Compute the CMR of a jet of scribe(v) : ONE |- TWO^(2^n) that outputs a given bitstring. * * Precondition: 2^n == value->len */
| 97 | * Precondition: 2^n == value->len |
| 98 | */ |
| 99 | sha256_midstate simplicity_computeWordCMR(const bitstring* value, size_t n) { |
| 100 | /* 'stack' is an array of 30 hashes consisting of 8 'uint32_t's each. */ |
| 101 | uint32_t stack[8*30] = {0}; |
| 102 | uint32_t *stack_ptr = stack; |
| 103 | sha256_midstate ih = identityIV; |
| 104 | simplicity_assert(n < 32); |
| 105 | simplicity_assert((size_t)1 << n == value->len); |
| 106 | /* Pass 1: Compute the CMR for the expression that writes 'value'. |
| 107 | * This expression consists of deeply nested PAIRs of expressions that write one bit each. |
| 108 | */ |
| 109 | /* stack[0..7] (8 bytes) is kept as all zeros for later. |
| 110 | * We start the stack_ptr at the second item. |
| 111 | */ |
| 112 | if (n < 3) { |
| 113 | stack_ptr += 8; |
| 114 | size_t i; |
| 115 | switch(n) { |
| 116 | case 0: i = getBit(value, 0); break; |
| 117 | case 1: i = 2 + ((1U * getBit(value, 0) << 1) | getBit(value, 1)); break; |
| 118 | case 2: i = 6 + ((1U * getBit(value, 0) << 3) | (1U * getBit(value, 1) << 2) | (1U * getBit(value, 2) << 1) | getBit(value, 3)); break; |
| 119 | } |
| 120 | memcpy(stack_ptr, &word_cmr[i], sizeof(uint32_t[8])); |
| 121 | } else { |
| 122 | for (size_t i = 0; i < value->len >> 3; ++i) { |
| 123 | /* stack_ptr == stack + 8*<count of the number of set bits in the value i> */ |
| 124 | stack_ptr += 8; |
| 125 | memcpy(stack_ptr, &word_cmr[22 + getByte(value, 8*i)], sizeof(uint32_t[8])); |
| 126 | /* This inner for loop runs in amortized constant time. */ |
| 127 | for (size_t j = i; j & 1; j = j >> 1) { |
| 128 | sha256_midstate pair = cmrIV(PAIR); |
| 129 | stack_ptr -= 8; |
| 130 | simplicity_sha256_compression(pair.s, stack_ptr); |
| 131 | memcpy(stack_ptr, pair.s, sizeof(uint32_t[8])); |
| 132 | } |
| 133 | } |
| 134 | } |
| 135 | /* value->len is a power of 2.*/ |
| 136 | simplicity_assert(stack_ptr == stack + 8); |
| 137 | |
| 138 | /* Pass 2: Compute the identity hash for the expression by adding the type roots of ONE and TWO^(2^n) to the CMR. */ |
| 139 | simplicity_sha256_compression(ih.s, stack); |
| 140 | memcpy(&stack[0], word_type_root[0].s, sizeof(uint32_t[8])); |
| 141 | memcpy(&stack[8], word_type_root[n+1].s, sizeof(uint32_t[8])); |
| 142 | simplicity_sha256_compression(ih.s, stack); |
| 143 | |
| 144 | /* Pass 3: Compute the jet's CMR from the specificion's identity hash. */ |
| 145 | return mkJetCMR(ih.s, ((uint_fast64_t)1 << n)); |
| 146 | } |
| 147 | |
| 148 | /* Given a well-formed dag[i + 1], such that for all 'j', 0 <= 'j' < 'i', |
| 149 | * 'dag[j].cmr' is the CMR of the subexpression denoted by the slice |
no test coverage detected