1module Model.Word32
2
3import Model.Config
4import Std.Byte
5import Std.Natural
6
7family ModelWord32ArithmeticErrorCode : Type 0
8constructor ModelWord32ModuloByZero
9
10end-family
11
12family ModelWord32ModuloResult : Type 0
13constructor ModelWord32ModuloSucceeded
14field unrestricted modelWord32ModuloValue : Nat
15constructor ModelWord32ModuloFailed
16field unrestricted modelWord32ModuloError : (family ModelWord32ArithmeticErrorCode)
17
18end-family
19
20family ModelWord32MultiplyState : Type 0
21constructor ModelWord32MultiplyStateValue
22field unrestricted modelWord32MultiplyMultiplicand : (family ModelWord32)
23field unrestricted modelWord32MultiplyMultiplier : (family ModelWord32)
24field unrestricted modelWord32MultiplyProduct : (family ModelWord32)
25
26end-family
27
28def modelWord32ArithmeticErrorCodeBytes =
29 (lambda unrestricted code : (family ModelWord32ArithmeticErrorCode) .
30 eliminate
31 ModelWord32ArithmeticErrorCode
32 (lambda unrestricted current : (family ModelWord32ArithmeticErrorCode) . Bytes)
33 code
34 (branch ModelWord32ModuloByZero . b"ALPHA-MODEL-001"))
35
36def modelWord32Zero =
37 (constructor ModelWord32 ModelWord32Value 0 0 0 0)
38
39def modelWord32NaturalOne =
40 1
41
42def modelWord32NaturalSeven =
43 7
44
45def modelWord32NaturalThirtyTwo =
46 32
47
48def modelWord32Select =
49 (lambda unrestricted condition : Nat .
50 unrestricted whenTrue : (family ModelWord32) .
51 unrestricted whenFalse : (family ModelWord32) .
52 nat-eliminate
53 (lambda unrestricted current : Nat . family ModelWord32)
54 whenFalse
55 (lambda unrestricted predecessor : Nat . unrestricted induction : (family ModelWord32) .
56 whenTrue)
57 condition)
58
59def modelWord32Xor =
60 (lambda unrestricted left : (family ModelWord32) . unrestricted right : (family ModelWord32) .
61 eliminate
62 ModelWord32
63 (lambda unrestricted current : (family ModelWord32) . family ModelWord32)
64 left
65 (branch
66 ModelWord32Value
67 l0
68 l1
69 l2
70 l3
71 .
72 eliminate
73 ModelWord32
74 (lambda unrestricted current : (family ModelWord32) . family ModelWord32)
75 right
76 (branch
77 ModelWord32Value
78 r0
79 r1
80 r2
81 r3
82 .
83 constructor
84 ModelWord32
85 ModelWord32Value
86 (byteXor l0 r0)
87 (byteXor l1 r1)
88 (byteXor l2 r2)
89 (byteXor l3 r3))))
90
91def modelWord32Add =
92 (lambda unrestricted left : (family ModelWord32) . unrestricted right : (family ModelWord32) .
93 eliminate
94 ModelWord32
95 (lambda unrestricted current : (family ModelWord32) . family ModelWord32)
96 left
97 (branch
98 ModelWord32Value
99 l0
100 l1
101 l2
102 l3
103 .
104 eliminate
105 ModelWord32
106 (lambda unrestricted current : (family ModelWord32) . family ModelWord32)
107 right
108 (branch
109 ModelWord32Value
110 r0
111 r1
112 r2
113 r3
114 .
115 eliminate
116 ByteAddResult
117 (lambda unrestricted current : (family ByteAddResult) . family ModelWord32)
118 (byteAddWithCarry l0 r0 0)
119 (branch
120 ByteAddResultValue
121 sum0
122 carry0
123 .
124 eliminate
125 ByteAddResult
126 (lambda unrestricted current : (family ByteAddResult) . family ModelWord32)
127 (byteAddWithCarry l1 r1 carry0)
128 (branch
129 ByteAddResultValue
130 sum1
131 carry1
132 .
133 eliminate
134 ByteAddResult
135 (lambda unrestricted current : (family ByteAddResult) . family ModelWord32)
136 (byteAddWithCarry l2 r2 carry1)
137 (branch
138 ByteAddResultValue
139 sum2
140 carry2
141 .
142 eliminate
143 ByteAddResult
144 (lambda unrestricted current : (family ByteAddResult) .
145 family ModelWord32)
146 (byteAddWithCarry l3 r3 carry2)
147 (branch
148 ByteAddResultValue
149 sum3
150 carry3
151 .
152 constructor ModelWord32 ModelWord32Value sum0 sum1 sum2 sum3)))))))
153
154def modelWord32ShiftRightOne =
155 (lambda unrestricted value : (family ModelWord32) .
156 eliminate
157 ModelWord32
158 (lambda unrestricted current : (family ModelWord32) . family ModelWord32)
159 value
160 (branch
161 ModelWord32Value
162 b0
163 b1
164 b2
165 b3
166 .
167 constructor
168 ModelWord32
169 ModelWord32Value
170 (byteOr
171 (byteShiftRight b0 modelWord32NaturalOne)
172 (byteShiftLeftTruncated (byteAnd b1 1) modelWord32NaturalSeven))
173 (byteOr
174 (byteShiftRight b1 modelWord32NaturalOne)
175 (byteShiftLeftTruncated (byteAnd b2 1) modelWord32NaturalSeven))
176 (byteOr
177 (byteShiftRight b2 modelWord32NaturalOne)
178 (byteShiftLeftTruncated (byteAnd b3 1) modelWord32NaturalSeven))
179 (byteShiftRight b3 modelWord32NaturalOne)))
180
181def modelWord32ShiftLeftOne =
182 (lambda unrestricted value : (family ModelWord32) .
183 eliminate
184 ModelWord32
185 (lambda unrestricted current : (family ModelWord32) . family ModelWord32)
186 value
187 (branch
188 ModelWord32Value
189 b0
190 b1
191 b2
192 b3
193 .
194 constructor
195 ModelWord32
196 ModelWord32Value
197 (byteShiftLeftTruncated b0 modelWord32NaturalOne)
198 (byteOr
199 (byteShiftLeftTruncated b1 modelWord32NaturalOne)
200 (byteShiftRight b0 modelWord32NaturalSeven))
201 (byteOr
202 (byteShiftLeftTruncated b2 modelWord32NaturalOne)
203 (byteShiftRight b1 modelWord32NaturalSeven))
204 (byteOr
205 (byteShiftLeftTruncated b3 modelWord32NaturalOne)
206 (byteShiftRight b2 modelWord32NaturalSeven))))
207
208def modelWord32ToNatural =
209 (lambda unrestricted value : (family ModelWord32) .
210 eliminate
211 ModelWord32
212 (lambda unrestricted current : (family ModelWord32) . Nat)
213 value
214 (branch
215 ModelWord32Value
216 b0
217 b1
218 b2
219 b3
220 .
221 then (naturalAdd (byte-to-nat b0))
222 (naturalMultiply byteNaturalTwoHundredFiftySix)
223 (naturalAdd (byte-to-nat b1))
224 (naturalMultiply byteNaturalTwoHundredFiftySix)
225 (naturalAdd (byte-to-nat b2))
226 (naturalMultiply byteNaturalTwoHundredFiftySix)
227 byte-to-nat
228 b3))
229
230-- General path: four divisions by 256 (a fold over the value each). Reached
231-- only for values of 256 and above; `modelWord32FromNaturalTruncated` takes
232-- the O(1) byte path below that (D17).
233def modelWord32FromNaturalDivided =
234 (lambda unrestricted value : Nat .
235 app
236 (lambda unrestricted quotient1 : Nat .
237 app
238 (lambda unrestricted quotient2 : Nat .
239 app
240 (lambda unrestricted quotient3 : Nat .
241 constructor
242 ModelWord32
243 ModelWord32Value
244 (nat-to-byte (naturalModuloUnchecked value byteNaturalTwoHundredFiftySix))
245 (nat-to-byte (naturalModuloUnchecked quotient1 byteNaturalTwoHundredFiftySix))
246 (nat-to-byte (naturalModuloUnchecked quotient2 byteNaturalTwoHundredFiftySix))
247 (nat-to-byte (naturalModuloUnchecked quotient3 byteNaturalTwoHundredFiftySix)))
248 (naturalDivideUnchecked quotient2 byteNaturalTwoHundredFiftySix))
249 (naturalDivideUnchecked quotient1 byteNaturalTwoHundredFiftySix))
250 (naturalDivideUnchecked value byteNaturalTwoHundredFiftySix))
251
252def modelWord32FromNaturalTruncated =
253 (lambda unrestricted value : Nat .
254 app
255 (nat-eliminate
256 (lambda unrestricted small : Nat . pi unrestricted unit : Nat . family ModelWord32)
257 (lambda unrestricted unit : Nat . modelWord32FromNaturalDivided value)
258 (lambda unrestricted predecessor : Nat .
259 unrestricted induction : (pi unrestricted unit : Nat . family ModelWord32) .
260 unrestricted unit : Nat .
261 constructor ModelWord32 ModelWord32Value (nat-to-byte value) 0 0 0)
262 (nat-less-than value byteNaturalTwoHundredFiftySix))
263 0)
264
265-- A logical shift is division/multiplication by 2^amount followed by the
266-- word conversion, rather than amount separate carry traversals. The width
267-- guard is lazy: amounts >= 32 return zero without computing their power.
268-- On the bounded u64 runtime lane the largest admitted multiplication is
269-- (2^32 - 1) * 2^31 < 2^63, so no host overflow precedes truncation. Keeping
270-- the one-bit operations independent also leaves a byte-lane reference for
271-- the full shift tests. The Baguette realize profile run-430189202 motivated
272-- this change; equality of emitted bytes still needs artifact qualification.
273def modelWord32ShiftRight =
274 (lambda unrestricted value : (family ModelWord32) . unrestricted amount : Nat .
275 app
276 (nat-eliminate
277 (lambda unrestricted current : Nat . pi unrestricted unit : Nat . family ModelWord32)
278 (lambda unrestricted unit : Nat . modelWord32Zero)
279 (lambda unrestricted predecessor : Nat .
280 unrestricted induction : (pi unrestricted unit : Nat . family ModelWord32) .
281 unrestricted unit : Nat .
282 modelWord32FromNaturalTruncated
283 (naturalDivideUnchecked (modelWord32ToNatural value) (naturalPowerOfTwo amount)))
284 (naturalLess amount modelWord32NaturalThirtyTwo))
285 0)
286
287def modelWord32ShiftLeft =
288 (lambda unrestricted value : (family ModelWord32) . unrestricted amount : Nat .
289 app
290 (nat-eliminate
291 (lambda unrestricted current : Nat . pi unrestricted unit : Nat . family ModelWord32)
292 (lambda unrestricted unit : Nat . modelWord32Zero)
293 (lambda unrestricted predecessor : Nat .
294 unrestricted induction : (pi unrestricted unit : Nat . family ModelWord32) .
295 unrestricted unit : Nat .
296 modelWord32FromNaturalTruncated
297 (naturalMultiply (modelWord32ToNatural value) (naturalPowerOfTwo amount)))
298 (naturalLess amount modelWord32NaturalThirtyTwo))
299 0)
300
301def modelWord32LeastBit =
302 (lambda unrestricted value : (family ModelWord32) .
303 eliminate
304 ModelWord32
305 (lambda unrestricted current : (family ModelWord32) . Nat)
306 value
307 (branch ModelWord32Value b0 b1 b2 b3 . byte-to-nat (byteAnd b0 1)))
308
309def modelWord32MultiplyStep =
310 (lambda unrestricted state : (family ModelWord32MultiplyState) .
311 eliminate
312 ModelWord32MultiplyState
313 (lambda unrestricted current : (family ModelWord32MultiplyState) .
314 family ModelWord32MultiplyState)
315 state
316 (branch
317 ModelWord32MultiplyStateValue
318 multiplicand
319 multiplier
320 product
321 .
322 constructor
323 ModelWord32MultiplyState
324 ModelWord32MultiplyStateValue
325 (modelWord32ShiftLeftOne multiplicand)
326 (modelWord32ShiftRightOne multiplier)
327 (modelWord32Select
328 (modelWord32LeastBit multiplier)
329 (modelWord32Add product multiplicand)
330 product)))
331
332def modelWord32MultiplyStateRun =
333 (lambda unrestricted left : (family ModelWord32) . unrestricted right : (family ModelWord32) .
334 nat-eliminate
335 (lambda unrestricted current : Nat . family ModelWord32MultiplyState)
336 (constructor
337 ModelWord32MultiplyState
338 ModelWord32MultiplyStateValue
339 left
340 right
341 modelWord32Zero)
342 (lambda unrestricted predecessor : Nat .
343 unrestricted induction : (family ModelWord32MultiplyState) .
344 modelWord32MultiplyStep induction)
345 modelWord32NaturalThirtyTwo)
346
347def modelWord32Multiply =
348 (lambda unrestricted left : (family ModelWord32) . unrestricted right : (family ModelWord32) .
349 eliminate
350 ModelWord32MultiplyState
351 (lambda unrestricted current : (family ModelWord32MultiplyState) . family ModelWord32)
352 (modelWord32MultiplyStateRun left right)
353 (branch ModelWord32MultiplyStateValue multiplicand multiplier product . product))
354
355def modelWord32ModuloStep =
356 (lambda unrestricted remainder : Nat . unrestricted value : Byte . unrestricted divisor : Nat .
357 naturalModuloUnchecked
358 (naturalAdd (naturalMultiply remainder byteNaturalTwoHundredFiftySix) (byte-to-nat value))
359 divisor)
360
361def modelWord32ModuloUnchecked =
362 (lambda unrestricted value : (family ModelWord32) . unrestricted divisor : Nat .
363 eliminate
364 ModelWord32
365 (lambda unrestricted current : (family ModelWord32) . Nat)
366 value
367 (branch
368 ModelWord32Value
369 b0
370 b1
371 b2
372 b3
373 .
374 modelWord32ModuloStep
375 (pipe 0
376 (modelWord32ModuloStep b3 divisor)
377 (modelWord32ModuloStep b2 divisor)
378 (modelWord32ModuloStep b1 divisor))
379 b0
380 divisor))
381
382def modelWord32Modulo =
383 (lambda unrestricted value : (family ModelWord32) . unrestricted divisor : Nat .
384 nat-eliminate
385 (lambda unrestricted current : Nat . family ModelWord32ModuloResult)
386 (constructor
387 ModelWord32ModuloResult
388 ModelWord32ModuloFailed
389 (constructor ModelWord32ArithmeticErrorCode ModelWord32ModuloByZero))
390 (lambda unrestricted predecessor : Nat .
391 unrestricted induction : (family ModelWord32ModuloResult) .
392 constructor
393 ModelWord32ModuloResult
394 ModelWord32ModuloSucceeded
395 (modelWord32ModuloUnchecked value divisor))
396 divisor)
397
398-- Successor modulo 2^32: one carry chain, no fold over the value (D17).
399def modelWord32Increment =
400 (lambda unrestricted value : (family ModelWord32) . modelWord32Add value modelWord32One)
401
402-- Order one byte position: 1 when left is below right, 0 when above, and the
403-- lower positions' verdict when equal (most significant position outermost).
404def modelWord32OrderByte =
405 (lambda unrestricted left : Byte . unrestricted right : Byte . unrestricted equalResult : Nat .
406 nat-eliminate
407 (lambda unrestricted less : Nat . Nat)
408 (nat-eliminate
409 (lambda unrestricted greater : Nat . Nat)
410 equalResult
411 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . 0)
412 (byte-less-than right left))
413 (lambda unrestricted predecessor : Nat . unrestricted induction : Nat . 1)
414 (byte-less-than left right))
415
416-- Unsigned order in four byte comparisons (D17).
417def modelWord32LessThan =
418 (lambda unrestricted left : (family ModelWord32) . unrestricted right : (family ModelWord32) .
419 eliminate
420 ModelWord32
421 (lambda unrestricted current : (family ModelWord32) . Nat)
422 left
423 (branch
424 ModelWord32Value
425 l0
426 l1
427 l2
428 l3
429 .
430 eliminate
431 ModelWord32
432 (lambda unrestricted current : (family ModelWord32) . Nat)
433 right
434 (branch
435 ModelWord32Value
436 r0
437 r1
438 r2
439 r3
440 .
441 then (modelWord32OrderByte l3 r3)
442 (modelWord32OrderByte l2 r2)
443 (modelWord32OrderByte l1 r1)
444 (modelWord32OrderByte l0 r0)
445 0)))
446
447def modelWord32Equal =
448 (lambda unrestricted left : (family ModelWord32) . unrestricted right : (family ModelWord32) .
449 naturalAnd
450 (naturalIsZero (modelWord32LessThan left right))
451 (naturalIsZero (modelWord32LessThan right left)))
452
453-- value × 10 = (value << 3) + (value << 1), modulo 2^32.
454def modelWord32TimesTen =
455 (lambda unrestricted value : (family ModelWord32) .
456 modelWord32Add
457 (modelWord32ShiftLeftOne (modelWord32ShiftLeftOne (modelWord32ShiftLeftOne value)))
458 (modelWord32ShiftLeftOne value))
459
460-- The value of one ASCII decimal digit byte (0x30..0x39) as a word.
461def modelWord32DecimalDigit =
462 (lambda unrestricted digit : Byte .
463 constructor ModelWord32 ModelWord32Value (byteAnd digit 15) 0 0 0)
464
465-- Decimal digit bytes, most significant first, to a word modulo 2^32; one
466-- step per digit. Callers check the bytes are digits and the value fits.
467def modelWord32FromDecimalDigitsTruncated =
468 (lambda unrestricted digits : Bytes .
469 app
470 (bytes-eliminate
471 (lambda unrestricted current : Bytes . pi unrestricted accumulator : (family ModelWord32) .
472 family ModelWord32)
473 (lambda unrestricted accumulator : (family ModelWord32) . accumulator)
474 (lambda unrestricted head : Byte .
475 unrestricted tail : Bytes .
476 unrestricted induction : (pi unrestricted accumulator : (family ModelWord32) . family ModelWord32) .
477 unrestricted accumulator : (family ModelWord32) .
478 induction
479 (modelWord32Add (modelWord32TimesTen accumulator) (modelWord32DecimalDigit head)))
480 digits)
481 modelWord32Zero)The compiler supplied declaration spans and resolved links from this source snapshot. This page does not assert that this file belongs to a checked closure.