1 # RFC ls003 Big Integer
5 * <https://libre-soc.org/openpower/sv/biginteger/analysis/>
6 * <https://libre-soc.org/openpower/sv/rfc/ls003/>
7 * <https://bugs.libre-soc.org/show_bug.cgi?id=960>
8 * <https://git.openpower.foundation/isa/PowerISA/issues/91>
20 **Books and Section affected**: **UPDATE**
23 Book I 64-bit Fixed-Point Arithmetic Instructions 3.3.9.1
24 Appendix E Power ISA sorted by opcode
25 Appendix F Power ISA sorted by version
26 Appendix G Power ISA sorted by Compliancy Subset
27 Appendix H Power ISA sorted by mnemonic
34 maddedu - Multiply-Add Extended Double Unsigned
35 divmod2du - Divide/Modulo Quad-Double Unsigned
38 **Submitter**: Luke Leighton (Libre-SOC)
40 **Requester**: Libre-SOC
42 **Impact on processor**:
45 Addition of two new GPR-based instructions
48 **Impact on software**:
51 Requires support for new instructions in assembler, debuggers,
58 GPR, Big-integer, Double-word
63 Similar to `maddhdu` and `maddld`, but allow for a big-integer rolling
64 accumulation affect: `RC` effectively becomes a 64-bit carry in chains
65 of highly efficient loop-unrolled arbitrary-length big-integer operations.
66 Similar to `divdeu`, and has similar advantages to `maddedu`,
67 Modulo result is available with the quotient.
69 **Notes and Observations**:
71 1. There is no need for an Rc=1 variant as VA-Form is being used.
72 2. There is no need for Special Registers as VA-Form is being used.
73 3. Both instructions have been present in Intel x86 for several decades.
74 4. Neither instruction is present in VSX: these are 128/64 whereas
76 5. `maddedu` and `divmod2du` are inverses of each other, including
77 when used for arbitrary-length big-integer arithmetic
81 Add the following entries to:
83 * the Appendices of Book I
84 * Instructions of Book I added to Section 3.3.9.1
90 # Multiply-Add Extended Double Unsigned
92 `maddedu RT, RA, RB, RC`
94 | 0-5 | 6-10 | 11-15 | 16-20 | 21-25 | 26-31 | Form |
95 |-------|------|-------|-------|-------|-------|---------|
96 | EXT04 | RT | RA | RB | RC | XO | VA-Form |
101 prod[0:127] <- (RA) * (RB) # Multiply RA and RB, result 128-bit
102 sum[0:127] <- EXTZ(RC) + prod # Zero extend RC, add product
103 RT <- sum[64:127] # Store low half in RT
104 RS <- sum[0:63] # RS implicit register, equal to RC
107 Special registers altered:
111 RC is zero-extended (not shifted, not sign-extended), the 128-bit product added
112 to it; the lower half of that result stored in RT and the upper half
115 The differences here to `maddhdu` are that `maddhdu` stores the upper
116 half in RT, where `maddedu` stores the upper half in RS.
118 The value stored in RT is exactly equivalent to `maddld` despite `maddld`
119 performing sign-extension on RC, because RT is the full mathematical result
120 modulo 2^64 and sign/zero extension from 64 to 128 bits produces identical
121 results modulo 2^64. This is why there is no maddldu instruction.
123 RS is implictly defined as the same register as RC.
126 As a Scalar Power ISA operation, like `lq` and `stq`, RS=RT+1.
127 To achieve a big-integer rolling-accumulation effect:
128 assuming the scalar to multiply is in r0,
129 the vector to multiply by starts at r4 and the result vector
130 in r20, instructions may be issued `maddedu r20,r4,r0,r20
131 maddedu r21,r5,r0,r21` etc. where the first `maddedu` will have
132 stored the upper half of the 128-bit multiply into r21, such
133 that it may be picked up by the second `maddedu`. Repeat inline
134 to construct a larger bigint scalar-vector multiply,
135 as Scalar GPR register file space permits.*
140 # (r0 * r1) + r2, store lower in r4, upper in r2
141 maddedu r4, r0, r1, r2
144 # Divide/Modulo Quad-Double Unsigned
146 **Should name be Divide/Module Double Extended Unsigned?**
147 **Check the pseudo-code comments**
149 `divmod2du RT,RA,RB,RC`
151 | 0-5 | 6-10 | 11-15 | 16-20 | 21-25 | 26-31 | Form |
152 |-------|------|-------|-------|-------|-------|---------|
153 | EXT04 | RT | RA | RB | RC | XO | VA-Form |
157 if ((RA) <u (RB)) & ((RB) != [0]*XLEN) then # Check RA<RB, for divide-by-0
158 dividend[0:(XLEN*2)-1] <- (RA) || (RC) # Combine RA/RC, zero extend
159 divisor[0:(XLEN*2)-1] <- [0]*XLEN || (RB) # Extend to 128-bit
160 result <- dividend / divisor # Division
161 modulo <- dividend % divisor # Modulo
162 RT <- result[XLEN:(XLEN*2)-1] # Store result in RT
163 RS <- modulo[XLEN:(XLEN*2)-1] # Modulo in RC, implicit
164 else # In case of error
165 RT <- [1]*XLEN # RT all 1's
166 RS <- [0]*XLEN # RS all 0's
168 Special registers altered:
172 Divide/Modulo Quad-Double Unsigned is another VA-Form instruction
173 that is near-identical to `divdeu` except that:
175 * the lower 64 bits of the dividend, instead of being zero, contain a
177 * it performs a fused divide and modulo in a single instruction, storing
178 the modulo in an implicit RS (similar to `maddedu`)
180 RB, the divisor, remains 64 bit. The instruction is therefore a 128/64
181 division, producing a (pair) of 64 bit result(s), in the same way that
182 Intel [divq](https://www.felixcloutier.com/x86/div) works.
184 are detected in exactly the same fashion as `divdeu`, except that rather
185 than have `UNDEFINED` behaviour, RT is set to all ones and RS set to all
188 *Programmer's note: there are no Rc variants of any of these VA-Form
189 instructions. `cmpi` will need to be used to detect overflow conditions:
190 the saving in instruction count is that both RT and RS will have already
191 been set to useful values (all 1s and all zeros respectively)
192 needed as part of implementing Knuth's
195 For Scalar usage, just as for `maddedu`, `RS=RC`
199 # ((r0 << 64) + r2) / r1, store in r4
200 # ((r0 << 64) + r2) % r1, store in r2
201 divmod2du r4, r0, r1, r2
208 Appendix E Power ISA sorted by opcode
209 Appendix F Power ISA sorted by version
210 Appendix G Power ISA sorted by Compliancy Subset
211 Appendix H Power ISA sorted by mnemonic
213 | Form | Book | Page | Version | mnemonic | Description |
214 |------|------|------|---------|----------|-------------|
215 | VA | I | # | 3.0B | maddedu | Multiply-Add Extend Double Unsigned |
216 | VA | I | # | 3.0B | divmod2du | Floatif Move | Divide/Modulo Quad-Double Unsigned