Source/Packages

Model.Word32

packages/foundation/standard/src/Model/Word32.alpha

481 lines41 declarations16.9 KiBSHA-256 56a6cf48ff83

Complete file · line 252

Word32.alpha

Definition view
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.