1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#include "frame.h"
#define READ_(bits,size) \
/* Given a read frame, return the value of the bits cells after the cursor and advance the frame's cursor by bits##. \
* The cell values are returned with the first cell in the MSB of the result and the last cell in the LSB of the result. \
* \
* Precondition: '*frame' is a valid read frame for bits more cells. \
*/ \
uint_fast##size##_t rustsimplicity_0_6_read##bits(frameItem* frame) { \
static_assert(bits <= size, "Return type too small to hold the requested number of bits."); \
uint_fast##size##_t result = 0; \
/* Pointers to the UWORD of the read frame that contains the frame's cursor (or is immediately after the cursor). */ \
UWORD* frame_ptr = frame->edge - 1 - frame->offset / UWORD_BIT; \
/* The specific bit within the above UWORD that is immediately in front of the cursor. \
* That bit is specifically '1 << (frame_shift - 1)'. \
*/ \
size_t frame_shift = UWORD_BIT - (frame->offset % UWORD_BIT); \
size_t n = bits; \
if (frame_shift < n) { \
/* We may only want part of the LSBs from the read frame's current UWORD. \
* Copy that data to 'x', and move the frame_ptr to the frame's next UWORD. \
*/ \
result |= (uint_fast##size##_t)((uint_fast##size##_t)LSBkeep(*frame_ptr, frame_shift) << (n - frame_shift)); \
frame->offset += frame_shift; \
n -= frame_shift; \
frame_shift = UWORD_BIT; \
frame_ptr--; \
while (UWORD_BIT < n) { \
/* Copy the entire read frame's current UWORD to 'x', and move the frame_ptr to the frame's next UWORD. */ \
result |= (uint_fast##size##_t)((uint_fast##size##_t)(*frame_ptr) << (n - UWORD_BIT)); \
frame->offset += UWORD_BIT; \
n -= UWORD_BIT; \
frame_ptr--; \
} \
} \
/* We may only want part of the bits from the middle of the read frame's current UWORD. \
* Copy that data to fill the remainder of 'x'. \
*/ \
result |= (uint_fast##size##_t)(LSBkeep((UWORD)(*frame_ptr >> (frame_shift - n)), n)); \
frame->offset += n; \
return result; \
}
READ_(4,8)
READ_(8,8)
READ_(16,16)
READ_(32,32)
READ_(64,64)
#define WRITE_(bits) \
/* Given a write frame, set the value of the bits cells after the cursor and advance the frame's cursor by bits##. \
* The first cell is set to the value of the MSB of 'x' and the last cell is set to the LSB of 'x'. \
* Cells in front of the cursor's final position may be overwritten. \
* \
* Precondition: '*frame' is a valid write frame for bits more cells. \
*/ \
void rustsimplicity_0_6_write##bits(frameItem* frame, uint_fast##bits##_t x) { \
/* Pointers to the UWORD of the write frame that contains the frame's cursor (or is immediately after the cursor). */ \
UWORD* frame_ptr = frame->edge + (frame->offset - 1) / UWORD_BIT; \
/* The specific bit within the above UWORD that is immediately in front of the cursor. \
* That bit is specifically '1 << (frame_shift - 1)'. \
*/ \
size_t frame_shift = (frame->offset - 1) % UWORD_BIT + 1; \
size_t n = bits; \
if (frame_shift < n) { \
/* The write frame's current UWORD may be partially filled. \
* Fill the rest of it with data from 'x', and move the frame_ptr to the frame's next UWORD. \
*/ \
*frame_ptr = LSBclear(*frame_ptr, frame_shift) | LSBkeep((UWORD)(x >> (n - frame_shift)), frame_shift); \
frame->offset -= frame_shift; \
n -= frame_shift; \
frame_shift = UWORD_BIT; \
frame_ptr--; \
while (UWORD_BIT < n) { \
/* Fill the write frame's entire current UWORD with data from 'x', and move the frame_ptr to the frame's next UWORD. */ \
*frame_ptr = (UWORD)(x >> (n - UWORD_BIT)); \
frame->offset -= UWORD_BIT; \
n -= UWORD_BIT; \
frame_ptr--; \
} \
} \
/* The current write frame's UWORD may be partially filled. \
* Fill the UWORD with the last of the data from 'x', which may or may not be enough to fill the rest of the UWORD. \
*/ \
*frame_ptr = (UWORD)(LSBclear(*frame_ptr, frame_shift) | (LSBkeep((UWORD)x, n) << (frame_shift - n))); \
frame->offset -= n; \
}
WRITE_(8)
WRITE_(16)
WRITE_(32)
WRITE_(64)
/* Read bytes from a Simplicity buffer of type (TWO^8)^<2^(n+1) into 'buf'.
* Set 'len' to the number of bytes read from the buffer.
* Advance the 'src' frame to the end of the buffer type.
*
* The notation X^<2 is notation for the type (S X)
* The notation X^<(2*n) is notation for the type S (X^n) * X^<n
*
* Precondition: unsigned char buf[2^(n+1)-1];
* NULL != len;
* '*src' is a valid read frame for 8*(2^(n+1)-1)+n+1 more cells;
* 0 <= n < 16
*/
void rustsimplicity_0_6_read_buffer8(unsigned char* buf, size_t* len, frameItem* src, int n) {
rustsimplicity_0_6_debug_assert(0 <= n && n < 16);
*len = 0;
for (size_t i = (size_t)1 << n; 0 < i; i /= 2) {
if (readBit(src)) {
read8s(buf, i, src);
buf += i; *len += i;
} else {
forwardBits(src, i*8);
}
}
}
/* Write 'len' bytes to a Simplicity buffer of type (TWO^8)^<2^(n+1) from 'buf'.
* Advance the 'dst' frame to the end of the buffer type.
*
* The notation X^<2 is notation for the type (S X)
* The notation X^<(2*n) is notation for the type S (X^n) * X^<n
*
* Precondition: '*dst' is a valid write frame for 8*(2^(n+1)-1)+n+1 more cells;
* unsigned char buf[len];
* len < 2^(n+1);
* 0 <= n < 16;
*/
void rustsimplicity_0_6_write_buffer8(frameItem* dst, const unsigned char* buf, size_t len, int n) {
rustsimplicity_0_6_debug_assert(0 <= n && n < 16);
rustsimplicity_0_6_debug_assert(len < ((size_t)1<<(n+1)));
for (size_t i = (size_t)1 << n; 0 < i; i /= 2) {
if (writeBit(dst, i <= len)) {
write8s(dst, buf, i);
buf += i; len -= i;
} else {
skipBits(dst, i*8);
}
}
}
/* Read data from a Simplicity CTX8 type (TWO^8)^<2^64 * TWO^64 * TWO^256 and fill in a sha256_context value.
* Advance the 'src' frame to the end of the CTX8 type.
* Returns false if the context's counter is too large (i.e. the compression count is greater than or equal to 2^55).
*
* The notation X^<2 is notation for the type (S X)
* The notation X^<(2*n) is notation for the type S (X^n) * X^<n
*
* Precondition: NULL != ctx->output;
* '*src' is a valid read frame for 838 more cells;
*/
bool rustsimplicity_0_6_read_sha256_context(sha256_context* ctx, frameItem* src) {
size_t len;
uint_fast64_t compressionCount;
rustsimplicity_0_6_read_buffer8(ctx->block, &len, src, 5);
compressionCount = rustsimplicity_0_6_read64(src);
ctx->counter = ((compressionCount*1U) << 6) + len;
read32s(ctx->output, 8, src);
ctx->overflow = (sha256_max_counter >> 6) <= compressionCount;
return !ctx->overflow;
}
/* Write data to a Simplicity CTX8 type (TWO^8)^<2^64 * TWO^64 * TWO^256 from a sha256_context value.
* Advance the 'dst' frame to the end of the CTX8 type.
* Returns false if the ctx had overflowed.
*
* The notation X^<2 is notation for the type (S X)
* The notation X^<(2*n) is notation for the type S (X^n) * X^<n
*
* Precondition: '*dst' is a valid write frame for 838 more cells;
* NULL != ctx->output;
* ctx->counter < 2^61;
*/
bool rustsimplicity_0_6_write_sha256_context(frameItem* dst, const sha256_context* ctx) {
rustsimplicity_0_6_write_buffer8(dst, ctx->block, ctx->counter % 64, 5);
rustsimplicity_0_6_write64(dst, ctx->counter >> 6);
write32s(dst, ctx->output, 8);
return !ctx->overflow;
}
/* Given a write frame and a read frame, copy 'n' cells from after the read frame's cursor to after the write frame's cursor,
* Cells in within the write frame beyond 'n' cells after the write frame's cursor may also be overwritten.
*
* Precondition: '*dst' is a valid write frame for 'n' more cells;
* '*src' is a valid read frame for 'n' more cells;
* '0 < n';
*/
static void copyBitsHelper(const frameItem* dst, const frameItem *src, size_t n) {
/* Pointers to the UWORDs of the read and write frame that contain the frame's cursor. */
UWORD* src_ptr = src->edge - 1 - src->offset / UWORD_BIT;
UWORD* dst_ptr = dst->edge + (dst->offset - 1) / UWORD_BIT;
/* The specific bit within those UWORDs that is immediately in front of their respective cursors.
* That bit is specifically '1 << (src_shift - 1)' for the read frame,
* and '1 << (dst_shift - 1)' for the write frame, unless 'dst_shift == 0', in which case it is '1 << (UWORD_BIT - 1)'.
*/
size_t src_shift = UWORD_BIT - (src->offset % UWORD_BIT);
size_t dst_shift = dst->offset % UWORD_BIT;
if (dst_shift) {
/* The write frame's current UWORD is partially filled.
* Fill the rest of it without overwriting the existing data.
*/
*dst_ptr = LSBclear(*dst_ptr, dst_shift);
if (src_shift < dst_shift) {
/* The read frame's current UWORD doesn't have enough data to entirely fill the rest of the write frame's current UWORD.
* Fill as much as we can and move src_ptr to the read frame's next UWORD.
*/
*dst_ptr |= (UWORD)(LSBkeep(*src_ptr, src_shift) << (dst_shift - src_shift));
if (n <= src_shift) return;
n -= src_shift;
dst_shift -= src_shift;
src_ptr--;
src_shift = UWORD_BIT;
}
/* Fill the rest of the write frame's current UWORD and move dst_ptr to the write frame's next UWORD. */
*dst_ptr |= LSBkeep((UWORD)(*src_ptr >> (src_shift - dst_shift)), dst_shift);
if (n <= dst_shift) return;
n -= dst_shift;
src_shift -= dst_shift;
dst_ptr--;
}
/* The next cell in the write frame to be filled begins at the boundary of a UWORD. */
/* :TODO: Use static analysis to limit the total amount of copied memory. */
if (0 == src_shift % UWORD_BIT) {
/* The next cell in the read frame to be filled also begins at the boundary of a UWORD.
* We can use 'memcpy' to copy data in bulk.
*/
size_t m = ROUND_UWORD(n);
/* If we went through the previous 'if (dst_shift)' block then 'src_shift == 0' and we need to decrement src_ptr.
* If we did not go through the previous 'if (dst_shift)' block then 'src_shift == UWORD_BIT'
* and we do not need to decrement src_ptr.
* We have folded this conditional decrement into the equation applied to 'src_ptr' below.
*/
memcpy(dst_ptr - (m - 1), src_ptr - (m - src_shift / UWORD_BIT), m * sizeof(UWORD));
} else {
while(1) {
/* Fill the write frame's UWORD by copying the LSBs of the read frame's current UWORD
* to the MSBs of the write frame's current UWORD,
* and copy the MSBs of the read frame's next UWORD to the LSBs of the write frame's current UWORD.
* Then move both the src_ptr and dst_ptr to their next UWORDs.
*/
*dst_ptr = (UWORD)(LSBkeep(*src_ptr, src_shift) << (UWORD_BIT - src_shift));
if (n <= src_shift) return;
*dst_ptr |= (UWORD)(*(src_ptr - 1) >> src_shift);
if (n <= UWORD_BIT) return;
n -= UWORD_BIT;
dst_ptr--; src_ptr--;
}
}
}
/* Given a write frame and a read frame, copy 'n' cells from after the read frame's cursor to after the write frame's cursor,
* and then advance the write frame's cursor by 'n'.
* Cells in front of the '*dst's cursor's final position may be overwritten.
*
* Precondition: '*dst' is a valid write frame for 'n' more cells;
* '*src' is a valid read frame for 'n' more cells;
*/
void rustsimplicity_0_6_copyBits(frameItem* dst, const frameItem* src, size_t n) {
if (0 == n) return;
copyBitsHelper(dst, src, n);
dst->offset -= n;
}