+/**
+ * creates a tarval from a condensed representation.
+ */
+static tarval *condensed_to_value(mul_env *env, unsigned char *R, int r) {
+ tarval *res, *tv;
+ int i, j;
+
+ j = 0;
+ tv = get_mode_one(env->mode);
+ res = NULL;
+ for (i = 0; i < r; ++i) {
+ j = R[i];
+ if (j) {
+ tarval *t = new_tarval_from_long(j, mode_Iu);
+ tv = tarval_shl(tv, t);
+ }
+ res = res ? tarval_add(res, tv) : tv;
+ }
+ return res;
+}
+
+/* forward */
+static instruction *basic_decompose_mul(mul_env *env, unsigned char *R, int r, tarval *N);
+
+/*
+ * handle simple cases with up-to 2 bits set
+ */
+static instruction *decompose_simple_cases(mul_env *env, unsigned char *R, int r, tarval *N) {
+ instruction *ins, *ins2;
+
+ (void) N;
+ if (r == 1) {
+ return emit_SHIFT(env, env->root, R[0]);
+ } else {
+ assert(r == 2);
+
+ ins = env->root;
+ if (R[1] <= env->max_S) {
+ ins = emit_LEA(env, ins, ins, R[1]);
+ if (R[0] != 0) {
+ ins = emit_SHIFT(env, ins, R[0]);
+ }
+ return ins;
+ }
+ if (R[0] != 0) {
+ ins = emit_SHIFT(env, ins, R[0]);
+ }
+
+ ins2 = emit_SHIFT(env, env->root, R[0] + R[1]);
+ return emit_LEA(env, ins, ins2, 0);
+ }
+}
+
+/**
+ * Main decompose driver.
+ */
+static instruction *decompose_mul(mul_env *env, unsigned char *R, int r, tarval *N) {
+ unsigned i;
+ int gain;
+
+ if (r <= 2)
+ return decompose_simple_cases(env, R, r, N);
+
+ if (params->also_use_subs) {
+ gain = calculate_gain(R, r);
+ if (gain > 0) {
+ instruction *instr1, *instr2;
+ unsigned char *R1, *R2;
+ int r1, r2, i, k, j;
+
+ R1 = complement_condensed(env, R, r, gain, &r1);
+ r2 = r - gain + 1;
+ R2 = obstack_alloc(&env->obst, r2);
+
+ k = 1;
+ for (i = 0; i < gain; ++i) {
+ k += R[i];
+ }
+ R2[0] = k;
+ R2[1] = R[gain] - 1;
+ j = 2;
+ if (R2[1] == 0) {
+ /* Two identical bits: normalize */
+ ++R2[0];
+ --j;
+ --r2;
+ }
+ for (i = gain + 1; i < r; ++i) {
+ R2[j++] = R[i];
+ }
+
+ instr1 = decompose_mul(env, R1, r1, NULL);
+ instr2 = decompose_mul(env, R2, r2, NULL);
+ return emit_SUB(env, instr2, instr1);
+ }
+ }
+
+ if (N == NULL)
+ N = condensed_to_value(env, R, r);
+
+ for (i = env->max_S; i > 0; --i) {
+ tarval *div_res, *mod_res;
+ tarval *tv = new_tarval_from_long((1 << i) + 1, env->mode);
+
+ div_res = tarval_divmod(N, tv, &mod_res);
+ if (mod_res == get_mode_null(env->mode)) {
+ unsigned char *Rs;
+ int rs;
+
+ Rs = value_to_condensed(env, div_res, &rs);
+ if (rs < r) {
+ instruction *N1 = decompose_mul(env, Rs, rs, div_res);
+ return emit_LEA(env, N1, N1, i);
+ }
+ }
+ }
+ return basic_decompose_mul(env, R, r, N);
+}
+
+#define IMAX(a,b) ((a) > (b) ? (a) : (b))
+
+/**
+ * basic decomposition routine
+ */
+static instruction *basic_decompose_mul(mul_env *env, unsigned char *R, int r, tarval *N) {
+ instruction *Ns;
+ unsigned t;
+
+ if (R[0] == 0) { /* Case 1 */
+ t = R[1] > IMAX(env->max_S, R[1]);
+ R[1] -= t;
+ Ns = decompose_mul(env, &R[1], r - 1, N);
+ return emit_LEA(env, env->root, Ns, t);
+ } else if (R[0] <= env->max_S) { /* Case 2 */
+ t = R[0];
+ R[1] += t;
+ Ns = decompose_mul(env, &R[1], r - 1, N);
+ return emit_LEA(env, Ns, env->root, t);
+ } else {
+ t = R[0];
+ R[0] = 0;
+ Ns = decompose_mul(env, R, r, N);
+ return emit_SHIFT(env, Ns, t);
+ }
+}