Given a compact bit representation of a value 'v : B', write the value 'v' to a write frame, skipping cells as needed * and advance its cursor. * Cells in front of the '*dst's cursor's final position may be overwritten. * * :TODO: Consider writing an optimized version of this function for word type 'TWO^(2^n)' which is a very common case and * doesn't need any skipping of cells. * * Precond
| 155 | * 'type_dag[typeIx]' is a type dag for the type B. |
| 156 | */ |
| 157 | static void writeValue(frameItem* dst, const bitstring* compactValue, size_t typeIx, type* type_dag) { |
| 158 | size_t cur = typeSkip(typeIx, type_dag); |
| 159 | size_t offset = 0; |
| 160 | bool calling = true; |
| 161 | setTypeBack(cur, type_dag, 0); |
| 162 | while (cur) { |
| 163 | if (SUM == type_dag[cur].kind) { |
| 164 | simplicity_debug_assert(calling); |
| 165 | |
| 166 | /* Write one bit to the write frame and then skip over any padding bits. */ |
| 167 | bool bit = getBit(compactValue, offset); |
| 168 | offset++; |
| 169 | writeBit(dst, bit); |
| 170 | skip(dst, pad(bit, type_dag[type_dag[cur].typeArg[0]].bitSize, type_dag[type_dag[cur].typeArg[1]].bitSize)); |
| 171 | |
| 172 | size_t next = typeSkip(type_dag[cur].typeArg[bit], type_dag); |
| 173 | if (next) { |
| 174 | setTypeBack(next, type_dag, type_dag[cur].back); |
| 175 | cur = next; |
| 176 | } else { |
| 177 | cur = type_dag[cur].back; |
| 178 | calling = false; |
| 179 | } |
| 180 | } else { |
| 181 | simplicity_debug_assert(PRODUCT == type_dag[cur].kind); |
| 182 | size_t next; |
| 183 | if (calling) { |
| 184 | next = typeSkip(type_dag[cur].typeArg[0], type_dag); |
| 185 | /* Note: Because we are using 'typeSkip' we have an invarant on 'cur' such that whenever type_dag[cur].kind == PRODUCT, |
| 186 | then it is a product of two non-trival types. This implies that 'next' cannot actually be 0. */ |
| 187 | if (next) { |
| 188 | /* Traverse the first element of the product type, if it has any data. */ |
| 189 | setTypeBack(next, type_dag, cur); |
| 190 | cur = next; |
| 191 | continue; |
| 192 | } |
| 193 | } |
| 194 | next = typeSkip(type_dag[cur].typeArg[1], type_dag); |
| 195 | /* Note: Because we are using 'typeSkip' we have an invarant on 'cur' such that whenever type_dag[cur].kind == PRODUCT, |
| 196 | then it is a product of two non-trival types. This implies that 'next' cannot actually be 0. */ |
| 197 | if (next) { |
| 198 | /* Traverse the second element of the product type, if it has any data. */ |
| 199 | setTypeBack(next, type_dag, type_dag[cur].back); |
| 200 | cur = next; |
| 201 | calling = true; |
| 202 | } else { |
| 203 | cur = type_dag[cur].back; |
| 204 | calling = false; |
| 205 | } |
| 206 | } |
| 207 | } |
| 208 | /* Note: Above we use 'typeSkip' to skip over long chains of products against trivial types |
| 209 | * This avoids a potential DOS vulnerability where a DAG of deeply nested products of unit types with sharing is traversed, |
| 210 | * taking exponential time. |
| 211 | * While traversing still could take exponential time in terms of the size of the type's dag, |
| 212 | * at least one bit of witness data is required per PRODUCT type encountered. |
| 213 | * This ought to limit the total number of times through the above loop to no more that 3 * compactValue->len. |
| 214 | */ |