Assembly (x86-64, AArch64, RISC-V) Module 5 – Arithmetic, logic and flags

Carries and 128-bit arithmetic

Build 128-bit and wider sums from 64-bit adds and their carries on x86-64, AArch64 and RISC-V, then check them and a 40-digit product against Python.

Intermediate
25 minutes
Examples run with Python 3.14.8 and Pyodide 314.0.7
By MySmartCoPilot

Free: the whole lesson. With a pass: the model answers to its 2 interview questions.

What you will learn

Build 128-bit and wider additions and subtractions from carry chains on x86-64 and AArch64
Implement the same carry and borrow logic on RISC-V with unsigned compares
Check multi-limb results against unsigned __int128 and against Python's integers
Compute a wide product from 64-bit partial products and the carries between them

Before you start

Flags and condition codes

What you’ll learn · Before you start

What you will learn

Build 128-bit and wider additions and subtractions from carry chains on x86-64 and AArch64
Implement the same carry and borrow logic on RISC-V with unsigned compares
Check multi-limb results against unsigned __int128 and against Python's integers
Compute a wide product from 64-bit partial products and the carries between them

Before you start

Flags and condition codes

On this page

A 64-bit register holds whole numbers below 2⁶⁴, about 1.8 × 10¹⁹, yet a 40-digit product, a 256-bit hash or a 2,048-bit key needs far more. No instruction adds two 256-bit numbers, but four 64-bit adds do, as long as each one hands its carry to the next.

This lesson builds 128-bit addition and subtraction from 64-bit pieces on x86-64 and AArch64, which keep the carry in a flag, and on RISC-V, which has none and finds each carry with a compare. You will extend them to loops over numbers of any length, multiply two-word numbers into four words, and check every result against two references: the 128-bit integers of GCC and Clang, and Python’s integers, which have no size limit.

A 128-bit sum is two adds joined by the carry

Add 1 to 2⁶⁴ − 1 in a 128-bit number. Each number is two 64-bit halves, a low and a high limb: One machine word of a number stored as several words, the name the GNU MP library uses: a 256-bit number on a 64-bit ISA is four 64-bit limbs, usually stored least significant first., the word the GNU MP manual uses for the part of a number that fits in one machine word. The low limbs, 0xffffffffffffffff and 1, add to 0 with a carry out of bit 63; the high limbs, 0 and 0, must then add to 1, which is the carry. That is the whole method: add the low limbs, then add the high limbs together with the carry the first add left.

Each ISA has an instruction for the second step. On x86-64, add sets CF and adc, add with carry, adds its two operands and CF. On AArch64 the pair is adds, which sets C, and adc, which adds C. Subtraction mirrors it with sub and sbb on x86-64 and subs and sbc on AArch64. The borrow keeps the opposite polarity on the two ISAs, as the flags lesson showed: sbb subtracts CF, which is 1 after a borrow, while sbc computes a + NOT b + C, which subtracts one more only when C is 0. Each pair is right for its own ISA.

add128 and sub128 on x86-64 and AArch64

x86-64 · x86_64/add128.s

# 128-bit add and subtract for x86-64, in GNU as Intel syntax. A number arrives as two 64-bit limbs:
# a = ahi:alo in rsi:rdi and b = bhi:blo in rcx:rdx. The result goes back in rdx:rax, high limb in rdx.
.intel_syntax noprefix
.text
.globl _add128
_add128:                    # u128 add128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi)
    mov rax, rdi
    add rax, rdx            # low limbs; CF = the carry out of bit 63
    mov rdx, rsi            # mov changes no flag, so CF survives
    adc rdx, rcx            # high limbs plus CF
    ret
.globl _sub128
_sub128:                    # u128 sub128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi)
    mov rax, rdi
    sub rax, rdx            # low limbs; CF = 1 when they needed a borrow
    mov rdx, rsi
    sbb rdx, rcx            # high limbs minus CF
    ret

AArch64 · aarch64/add128.s

// 128-bit add and subtract for AArch64. a = x1:x0 and b = x3:x2, low limb first; the result goes back in x1:x0.
.text
.p2align 2
.globl _add128
_add128:                    // u128 add128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi)
    adds x0, x0, x2         // low limbs; C = the carry out of bit 63
    adc x1, x1, x3          // high limbs plus C
    ret
.globl _sub128
_sub128:                    // u128 sub128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi)
    subs x0, x0, x2         // low limbs; C = 1 when no borrow was needed
    sbc x1, x1, x3          // high limbs: x1 + NOT x3 + C, which subtracts 1 more when C = 0
    ret

The four limbs arrive in the first four argument registers, rdi, rsi, rdx and rcx on x86-64 and x0 to x3 on AArch64. The result is a C struct of two 64-bit fields, which the x86-64 psABI returns in rax and then rdx, and AAPCS64 in x0 and x1. In the x86-64 version a mov sits between add and adc: it moves the high limb of a into rdx, the register that returns the high half, and it writes no flag, so CF reaches adc unchanged.

The results come from an Apple M5 Pro under macOS, where AArch64 code executes directly and Rosetta 2 translates the x86-64 build as it starts. The checker compares every result with unsigned __int128, the 128-bit integer type GCC and Clang provide:

add128.c: six sums and differences against unsigned __int128 C · add128.c

// Checks add128 and sub128 against unsigned __int128, the 128-bit integer type of GCC and Clang.
#include <stdint.h>
#include <stdio.h>

typedef struct { uint64_t lo, hi; } u128;
u128 add128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi);
u128 sub128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi);

typedef unsigned __int128 ref128;
static ref128 join(uint64_t hi, uint64_t lo) { return (ref128)hi << 64 | lo; }

static void check(const char *what, char op, uint64_t ahi, uint64_t alo, uint64_t bhi, uint64_t blo) {
    u128 r = op == '+' ? add128(alo, ahi, blo, bhi) : sub128(alo, ahi, blo, bhi);
    ref128 want = op == '+' ? join(ahi, alo) + join(bhi, blo) : join(ahi, alo) - join(bhi, blo);
    int ok = r.hi == (uint64_t)(want >> 64) && r.lo == (uint64_t)want;
    printf("%-16s hi %016llx  lo %016llx  %s\n", what, (unsigned long long)r.hi, (unsigned long long)r.lo,
           ok ? "ok" : "WRONG");
}

int main(void) {
    const uint64_t M = UINT64_MAX;
    check("(2^64 - 1) + 1", '+', 0, M, 0, 1);
    check("(2^128 - 1) + 1", '+', M, M, 0, 1);
    check("10^20 + 10^20", '+', 5, 0x6bc75e2d63100000, 5, 0x6bc75e2d63100000);
    check("2^64 - 1", '-', 1, 0, 0, 1);
    check("0 - 1", '-', 0, 0, 0, 1);
    check("10^20 - 10^19", '-', 5, 0x6bc75e2d63100000, 0, 0x8ac7230489e80000);
    return 0;
}

add128 and sub128 on AArch64 and on x86-64 Python · add128_session.py

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# The same checker against both assembly files; the x86-64 build runs through Rosetta 2.
session.run("""
clang -O1 -o add128_a64 add128.c aarch64/add128.s
./add128_a64 | tee a64.txt
clang -O1 -arch x86_64 -o add128_x64 add128.c x86_64/add128.s
./add128_x64 | diff a64.txt - && echo "x86-64 printed the same 6 lines"
""")

Output

$ clang -O1 -o add128_a64 add128.c aarch64/add128.s
$ ./add128_a64 | tee a64.txt
(2^64 - 1) + 1   hi 0000000000000001  lo 0000000000000000  ok
(2^128 - 1) + 1  hi 0000000000000000  lo 0000000000000000  ok
10^20 + 10^20    hi 000000000000000a  lo d78ebc5ac6200000  ok
2^64 - 1         hi 0000000000000000  lo ffffffffffffffff  ok
0 - 1            hi ffffffffffffffff  lo ffffffffffffffff  ok
10^20 - 10^19    hi 0000000000000004  lo e1003b28d9280000  ok
$ clang -O1 -arch x86_64 -o add128_x64 add128.c x86_64/add128.s
$ ./add128_x64 | diff a64.txt - && echo "x86-64 printed the same 6 lines"
x86-64 printed the same 6 lines

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 add128_session.py

All six lines say ok on both ISAs. The first is the sum from the start of this section, high limb 1 and low limb 0. The second, (2¹²⁸ − 1) + 1, shows the same wraparound one level up: the carry out of the high limb has nowhere to go, and the 128-bit result is 0. 0 - 1 borrows through both limbs and leaves all ones, which is −1 in 128-bit two’s complement. Step through one carry and one borrow crossing between the limbs:

Interactive · step by step A carry and a borrow crossing from the low limb to the high limb Step through (2^64 - 1) + 1 and then 2^64 - 1, done in two 64-bit limbs, with the high limb on the left as in a written number.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

Two 128-bit numbers. a = 2^64 - 1 and b = 1, each held as two 64-bit limbs. The high limbs are 0; the low limb of a is all ones.
Add the low limbs. add on x86-64, or adds on AArch64, adds the low limbs: ffff ffff ffff ffff + 1 wraps to 0, and a carry leaves bit 63.
The carry waits in a flag. The carry goes to CF on x86-64 and to C on AArch64. Instructions that write no flag, such as mov, can run in between without losing it.
Add the high limbs and the carry. adc adds the high limbs and the flag: 0 + 0 + 1 = 1. The result is high limb 1, low limb 0, which is 2^64, as the recorded first line shows.
Now subtract 2^64 - 1. a = 2^64 is high limb 1, low limb 0, and b = 1. sub of the low limbs, 0 - 1, wraps to all ones and needs a borrow: CF = 1 on x86-64, C = 0 on AArch64.
The high limbs pay the borrow. sbb on x86-64 and sbc on AArch64 subtract the high limbs and the borrow: 1 - 0 - 1 = 0. The result, 0 and all ones, is 2^64 - 1.

Starting the chain with adc

The low limb takes a plain add or adds. An adc there also adds whatever carry an earlier instruction left, so the sum is off by one only when that flag happened to be set, which makes the bug come and go. Start every chain with add, or clear the carry first.

Checkpoint

Check: Joining two 64-bit adds with the carry

Question 1 of 2 add128 adds a = 2^64 − 1 (high limb 0, low limb 0xffffffffffffffff) and b = 1. What is the high limb of the result?
Type a number.
Your answer

A hint

The low limbs wrap to 0. What does adc add to the high limbs?

Show the answer: Question 1 of 2

Answer: 1

The low add wraps to 0 and sets the carry. adc then adds the high limbs and the carry: 0 + 0 + 1 = 1. The result, high limb 1 and low limb 0, is 2^64, the first line of the recorded run.
Question 2 of 2 AArch64 sub128 computes (2^64) − 1: subs of the low limbs is 0 − 1. What do C and the following sbc do?
Choose one answer.

sbc ignores C and subtracts the high limbs only subs leaves C = 0, so sbc subtracts nothing extra and the high limb stays 1 subs leaves C = 0, a borrow, so sbc computes 1 − 0 − 1 = 0 for the high limb subs leaves C = 1, a borrow, so sbc subtracts 1

Show the answer: Question 2 of 2

Answer: subs leaves C = 0, a borrow, so sbc computes 1 − 0 − 1 = 0 for the high limb

0 − 1 needs a borrow, which AArch64 records as C = 0. sbc x1, x1, x3 is x1 + NOT x3 + C = x1 − x3 − 1 + C, so with C = 0 the high limb becomes 1 − 0 − 1 = 0, and the result is 2^64 − 1, as recorded.

RISC-V finds each carry with a compare

RISC-V has no flags, so add keeps the low 64 bits of a sum and nothing else. The carry can still be recovered. When an add wraps, the stored sum is the true sum minus 2⁶⁴, which is below either operand; when it does not, the sum is at least as large as both. So one unsigned compare after the add gives the carry: sltu t0, a0, a2 is 1 exactly when the new low limb is below the low limb of b. It is the check the RV32I chapter of the manual gives for unsigned overflow, written into a register instead of a branch. A borrow is simpler still: a − b borrows exactly when a is below b, so sltu compares the low limbs before the subtraction overwrites them.

add128 and sub128 on RISC-V S · riscv/add128.s

# 128-bit add and subtract for RV64I, which has no carry flag. a = a1:a0 and b = a3:a2, low limb first;
# the result goes back in a1:a0.
.text
.globl add128
add128:                     # u128 add128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi)
    add a0, a0, a2          # low limbs, wrapped to 64 bits
    sltu t0, a0, a2         # the carry: the wrapped sum is below blo exactly when the add carried
    add a1, a1, a3          # high limbs
    add a1, a1, t0          # plus the carry
    ret
.globl sub128
sub128:                     # u128 sub128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi)
    sltu t0, a0, a2         # the borrow: alo is below blo, compared before a0 is overwritten
    sub a0, a0, a2
    sub a1, a1, a3
    sub a1, a1, t0          # minus the borrow
    ret

macOS cannot run RISC-V programs. The method itself is plain C, though: add, then compare. carry.c writes add128 and sub128 that way, so it links with the same checker and runs natively, and the session then compiles it for each ISA:

carry.c: the RISC-V method written in C C · carry.c

// The RISC-V method written in C: add the limbs, then compare to find each carry or borrow. It compiles for, and
// runs on, every ISA, and links with the same checkers as the assembly files.
#include <stdint.h>

typedef struct { uint64_t lo, hi; } u128;

u128 add128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi) {
    u128 r;
    r.lo = alo + blo;
    uint64_t carry = r.lo < blo;  // 1 exactly when the low add wrapped
    r.hi = ahi + bhi + carry;
    return r;
}

u128 sub128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi) {
    u128 r;
    uint64_t borrow = alo < blo;  // 1 exactly when the low subtract wraps
    r.lo = alo - blo;
    r.hi = ahi - bhi - borrow;
    return r;
}

uint64_t add_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n) {
    uint64_t carry = 0;
    for (long i = 0; i < n; i++) {
        uint64_t s = a[i] + b[i];
        uint64_t c1 = s < b[i];   // carry out of a[i] + b[i]
        s += carry;
        uint64_t c2 = s < carry;  // carry out of adding the carry in
        r[i] = s;
        carry = c1 | c2;          // never both: see the lesson
    }
    return carry;
}

uint64_t sub_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n) {
    uint64_t borrow = 0;
    for (long i = 0; i < n; i++) {
        uint64_t b1 = a[i] < b[i];  // borrow out of a[i] - b[i]
        uint64_t d = a[i] - b[i];
        uint64_t b2 = d < borrow;   // borrow out of subtracting the borrow in
        r[i] = d - borrow;
        borrow = b1 | b2;
    }
    return borrow;
}

The C version runs, then compiles for three ISAs Python · carry_session.py

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# The RISC-V method in C runs natively against the same checker, then clang compiles it for each ISA at -O2.
# objdump --disassemble-symbols lists one function of an object file; -M intel picks Intel syntax for x86-64.
session.run("""
clang -O1 -o add128_c add128.c carry.c
./add128_c
clang -O2 -fomit-frame-pointer -arch x86_64 -c -o carry_x64.o carry.c
objdump -d --no-show-raw-insn -M intel --disassemble-symbols=_add128 carry_x64.o
clang -O2 -c -o carry_a64.o carry.c
objdump -d --no-show-raw-insn --disassemble-symbols=_add128 carry_a64.o
/opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc -O2 -c -o carry_rv.o carry.c
llvm-objdump -d --no-show-raw-insn --disassemble-symbols=add128 carry_rv.o
llvm-mc --triple=riscv64 -filetype=obj -o add128_rv.o riscv/add128.s
llvm-objdump -d --no-show-raw-insn --disassemble-symbols=add128 add128_rv.o
""")

Output

$ clang -O1 -o add128_c add128.c carry.c
$ ./add128_c
(2^64 - 1) + 1   hi 0000000000000001  lo 0000000000000000  ok
(2^128 - 1) + 1  hi 0000000000000000  lo 0000000000000000  ok
10^20 + 10^20    hi 000000000000000a  lo d78ebc5ac6200000  ok
2^64 - 1         hi 0000000000000000  lo ffffffffffffffff  ok
0 - 1            hi ffffffffffffffff  lo ffffffffffffffff  ok
10^20 - 10^19    hi 0000000000000004  lo e1003b28d9280000  ok
$ clang -O2 -fomit-frame-pointer -arch x86_64 -c -o carry_x64.o carry.c
$ objdump -d --no-show-raw-insn -M intel --disassemble-symbols=_add128 carry_x64.o

carry_x64.o:	file format mach-o 64-bit x86-64

Disassembly of section __TEXT,__text:

0000000000000000 <_add128>:
       0:      	mov	rax, rdi
       3:      	add	rax, rdx
       6:      	adc	rsi, rcx
       9:      	mov	rdx, rsi
       c:      	ret
       d:      	nop	dword ptr [rax]
$ clang -O2 -c -o carry_a64.o carry.c
$ objdump -d --no-show-raw-insn --disassemble-symbols=_add128 carry_a64.o

carry_a64.o:	file format mach-o arm64

Disassembly of section __TEXT,__text:

0000000000000000 <_add128>:
       0:      	adds	x0, x2, x0
       4:      	adc	x1, x3, x1
       8:      	ret
$ /opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc -O2 -c -o carry_rv.o carry.c
$ llvm-objdump -d --no-show-raw-insn --disassemble-symbols=add128 carry_rv.o

carry_rv.o:	file format elf64-littleriscv

Disassembly of section .text:

0000000000000000 <add128>:
       0:      	add	a0, a0, a2
       2:      	sltu	a2, a0, a2
       6:      	add	a1, a1, a3
       8:      	add	a1, a1, a2
       a:      	ret
$ llvm-mc --triple=riscv64 -filetype=obj -o add128_rv.o riscv/add128.s
$ llvm-objdump -d --no-show-raw-insn --disassemble-symbols=add128 add128_rv.o

add128_rv.o:	file format elf64-littleriscv

Disassembly of section .text:

0000000000000000 <add128>:
       0:      	add	a0, a0, a2
       4:      	sltu	t0, a0, a2
       8:      	add	a1, a1, a3
       c:      	add	a1, a1, t0
      10:      	ret

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 carry_session.py

The C version printed the same six ok lines. For RISC-V, clang produced the four instructions of the hand-written file, with a2 instead of t0 holding the carry. For x86-64 and AArch64 it recognised the compare as a carry and used the flag: add and adc, and adds and adc. Writing the carry as a comparison costs nothing on the flag-based ISAs and is exactly what RISC-V needs.

Inside a longer number a limb also has a carry coming in, and a[i] + b[i] + carry can carry at either of its two adds. The RISC-V loop of the next section compares after each add and combines the two answers with or. Step through one limb for two inputs where a different compare finds the carry:

Interactive · stage by stage One limb of the RISC-V add_n loop, with a carry coming in Step through the five instructions that add one limb and its carry, for two limbs where a different compare finds the carry.

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text

The first add carries. Take a[i] = 2^64 - 1, b[i] = 1 and a carry in of 1. a[i] + b[i] wraps to 0, and 0 is below b[i] = 1, so sltu writes t3 = 1.
The second add does not. Adding the carry in gives 1, which is not below the carry in, 1: t4 = 0. The limb is 1 and the carry out is 1, since 2^64 - 1 + 1 + 1 = 2^64 + 1.
Now only the carry in carries. Take a[i] = 2^64 - 1, b[i] = 0 and a carry in of 1. The first add gives 2^64 - 1, not below b[i] = 0, so t3 = 0.
The second compare finds it. Adding the carry in wraps to 0, which is below 1, so t4 = 1, and the carry out is 1: 2^64 - 1 + 0 + 1 = 2^64 is limb 0 with a carry.
Never both. When the first add carries, its wrapped sum is at most 2^64 - 2, so adding a carry of 1 cannot carry again. At most one of t3 and t4 is 1, and or combines them.

Key idea

Without a carry flag, a carry is a compare: when s = a + b wraps, s is below b, so sltu recovers it, and a − b borrows exactly when a is below b. With a carry coming in, each of the two adds gets its own compare, and at most one of them is 1.

Checkpoint

Check: Carries and borrows from compares on RISC-V

Question 1 of 2 After add a0, a0, a2 adds two low limbs on RISC-V, which instruction puts the carry in t0?
Choose one answer.

slt t0, a0, a2 sltu t0, a2, a0 sltu t0, a0, a2 srli t0, a0, 63

Show the answer: Question 1 of 2

Answer: sltu t0, a0, a2

With a carry the stored sum is a + b − 2^64, which is below b, because a < 2^64; without one it is a + b, at least b. sltu t0, a0, a2 turns that into 0 or 1, as clang also emitted for carry.c.
Question 2 of 2 RISC-V sub128 runs sltu t0, a0, a2 before sub a0, a0, a2. Why in that order?
Choose one answer.

After the sub, the borrow could no longer be found by any compare sub sets a borrow flag that sltu then reads sltu must run first because RISC-V executes compares before arithmetic The borrow is "alo is below blo", and sub overwrites a0, which holds alo

Show the answer: Question 2 of 2

Answer: The borrow is "alo is below blo", and sub overwrites a0, which holds alo

a − b borrows exactly when a < b as unsigned numbers. The comparison needs alo, and sub a0, a0, a2 writes the difference over it, so the file compares first. The add version compares after, against a2, which the add did not overwrite.

Numbers of any width are loops over limbs

A 512-bit number is eight limbs, and adding two of them is the 128-bit method run eight times, the carry passing from each limb to the next. Libraries store such a multi-precision integer: An integer wider than one register, stored as an array of limbs and handled by loops of word-sized instructions that pass carries from limb to limb; also called a big integer or bignum. as an array of limbs, least significant first, so limb i is worth 2⁶⁴ⁱ. add_n(r, a, b, n) adds two numbers of n limbs and returns the carry out of the top limb; sub_n returns the borrow:

add_n and sub_n in three ISAs

x86-64 · x86_64/add_n.s

# add_n and sub_n for x86-64, in GNU as Intel syntax: r = a + b or a - b, on numbers of n 64-bit limbs stored
# least significant first. They return the carry or borrow out of the top limb.
# Arguments: r in rdi, a in rsi, b in rdx, n in rcx.
.intel_syntax noprefix
.text
.globl _add_n
_add_n:                     # uint64_t add_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n)
    xor eax, eax            # i = 0; xor also clears CF for the first adc
    test rcx, rcx           # n = 0: nothing to add (test clears CF too)
    jz 2f
1:  mov r8, qword ptr [rsi + 8*rax]
    adc r8, qword ptr [rdx + 8*rax]    # a[i] + b[i] + CF; CF = the carry out
    mov qword ptr [rdi + 8*rax], r8
    inc rax                 # inc and dec leave CF alone,
    dec rcx                 # so it reaches the next adc
    jnz 1b
2:  setc al                 # the carry out of the top limb
    movzx eax, al
    ret
.globl _sub_n
_sub_n:                     # uint64_t sub_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n)
    xor eax, eax
    test rcx, rcx
    jz 2f
1:  mov r8, qword ptr [rsi + 8*rax]
    sbb r8, qword ptr [rdx + 8*rax]    # a[i] - b[i] - CF; CF = the borrow out
    mov qword ptr [rdi + 8*rax], r8
    inc rax
    dec rcx
    jnz 1b
2:  setc al                 # the borrow out of the top limb
    movzx eax, al
    ret

AArch64 · aarch64/add_n.s

// add_n and sub_n for AArch64: r = a + b or a - b, on numbers of n 64-bit limbs stored least significant first.
// They return the carry or borrow out of the top limb. Arguments: r in x0, a in x1, b in x2, n in x3.
.text
.p2align 2
.globl _add_n
_add_n:                     // uint64_t add_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n)
    cmn xzr, xzr            // 0 + 0: C = 0 for the first adcs
    cbz x3, 2f
1:  ldr x4, [x1], #8        // a[i], then a moves to the next limb
    ldr x5, [x2], #8        // b[i]
    adcs x4, x4, x5         // a[i] + b[i] + C; C = the carry out
    str x4, [x0], #8        // r[i]
    sub x3, x3, #1          // plain sub and cbnz leave C alone
    cbnz x3, 1b
2:  cset x0, cs             // the carry out of the top limb
    ret
.globl _sub_n
_sub_n:                     // uint64_t sub_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n)
    cmp xzr, xzr            // 0 - 0: C = 1, "no borrow", for the first sbcs
    cbz x3, 2f
1:  ldr x4, [x1], #8
    ldr x5, [x2], #8
    sbcs x4, x4, x5         // a[i] + NOT b[i] + C; C = 0 when this limb borrowed
    str x4, [x0], #8
    sub x3, x3, #1
    cbnz x3, 1b
2:  cset x0, cc             // borrow out = C clear
    ret

RISC-V · riscv/add_n.s

# add_n and sub_n for RV64I: r = a + b or a - b, on numbers of n 64-bit limbs stored least significant first.
# They return the carry or borrow out of the top limb. Arguments: r in a0, a in a1, b in a2, n in a3.
.text
.globl add_n
add_n:                      # uint64_t add_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n)
    li t0, 0                # the carry in
    beqz a3, 2f
1:  ld t1, 0(a1)            # a[i]
    ld t2, 0(a2)            # b[i]
    add t1, t1, t2
    sltu t3, t1, t2         # carry out of a[i] + b[i]
    add t1, t1, t0
    sltu t4, t1, t0         # carry out of adding the carry in
    or t0, t3, t4           # never both
    sd t1, 0(a0)
    addi a0, a0, 8
    addi a1, a1, 8
    addi a2, a2, 8
    addi a3, a3, -1
    bnez a3, 1b
2:  mv a0, t0
    ret
.globl sub_n
sub_n:                      # uint64_t sub_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n)
    li t0, 0                # the borrow in
    beqz a3, 2f
1:  ld t1, 0(a1)
    ld t2, 0(a2)
    sltu t3, t1, t2         # borrow out of a[i] - b[i]
    sub t1, t1, t2
    sltu t4, t1, t0         # borrow out of subtracting the borrow in
    sub t1, t1, t0
    or t0, t3, t4
    sd t1, 0(a0)
    addi a0, a0, 8
    addi a1, a1, 8
    addi a2, a2, 8
    addi a3, a3, -1
    bnez a3, 1b
2:  mv a0, t0
    ret

The hard part of these loops is keeping the carry alive between iterations. A carry chain: A sequence of additions or subtractions in which each step takes in the carry or borrow of the step below it: add then adc on x86-64, adds then adcs on AArch64, or add and sltu on RISC-V. runs through every limb, so every instruction between two adc has to leave the carry alone. On x86-64 that rules out add and sub for the loop’s index and counter: the loop uses inc and dec, which leave CF untouched, and jnz tests the ZF that dec set. On AArch64 a plain sub writes no flag at all, and cbnz branches on a register without reading NZCV. RISC-V keeps its carry in an ordinary register, t0, so nothing in the loop can disturb it, but it pays for the carry with two compares and an or per limb:

Loop body per limb	Instructions	The carry lives in
x86-64: `mov`, `adc`, `mov`, `inc`, `dec`, `jnz`	6	CF
AArch64: `ldr`, `ldr`, `adcs`, `str`, `sub`, `cbnz`	6	C
RISC-V: 2 `ld`, `add`, `sltu`, `add`, `sltu`, `or`, `sd`, 4 `addi`, `bnez`	13	`t0`

Wider numbers need a second reference, since unsigned __int128 stops at two limbs. Python’s integers have unlimited precision, as its documentation puts it, and share no code with the assembly. wide.c adds and subtracts numbers of 1, 2, 4 and 8 limbs, 64 to 512 bits, and writes every operand and result in hex; check_wide.py reads the lines back and recomputes each one with Python’s integers:

wide.c: 34 additions and subtractions of up to 512 bits C · wide.c

// Adds and subtracts numbers of 1, 2, 4 and 8 limbs (64 to 512 bits) with add_n and sub_n, and prints every
// operand and result in hex, most significant limb first, for an independent checker. The limbs come from a fixed
// pseudo-random sequence (splitmix64), so every run prints the same numbers.
#include <stdint.h>
#include <stdio.h>

uint64_t add_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n);
uint64_t sub_n(uint64_t *r, const uint64_t *a, const uint64_t *b, long n);

static uint64_t state = 2026;
static uint64_t next(void) {  // splitmix64
    uint64_t z = (state += 0x9e3779b97f4a7c15);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
    return z ^ (z >> 31);
}

static void hex(const uint64_t *x, long n) {
    for (long i = n - 1; i >= 0; i--) printf("%016llx", (unsigned long long)x[i]);
}

static void line(char op, const uint64_t *a, const uint64_t *b, long n) {
    uint64_t r[8];
    uint64_t c = op == '+' ? add_n(r, a, b, n) : sub_n(r, a, b, n);
    printf("%c %ld ", op, n);
    hex(a, n), printf(" "), hex(b, n), printf(" "), hex(r, n);
    printf(" %llu\n", (unsigned long long)c);
}

int main(void) {
    uint64_t a[8], b[8];
    for (int round = 0; round < 4; round++) {
        for (long n = 1; n <= 8; n *= 2) {
            for (long i = 0; i < n; i++) a[i] = next(), b[i] = next();
            line('+', a, b, n);
            line('-', a, b, n);
        }
    }
    for (long i = 0; i < 8; i++) a[i] = UINT64_MAX, b[i] = i == 0;  // 2^512 - 1 and 1
    line('+', a, b, 8);  // every limb carries: 0 with a carry out of 1
    line('-', b, a, 8);  // 1 - (2^512 - 1) borrows: 2, borrow out 1
    return 0;
}

check_wide.py: the independent reference Python · check_wide.py

"""Checks the lines wide.c prints with Python's integers, which have no width limit: a reference that shares no code
with the assembly."""


def check(path: str) -> None:
    lines = open(path).read().split("\n")[:-1]
    bad = 0
    for text in lines:
        op, n, a, b, r, out = text.split()
        bits = 64 * int(n)
        a, b, r, out = int(a, 16), int(b, 16), int(r, 16), int(out)
        exact = a + b if op == "+" else a - b
        # The limbs keep the low bits; the carry or borrow out is the part that did not fit.
        want_r = exact % 2**bits
        want_out = 1 if exact >= 2**bits or exact < 0 else 0
        if (r, out) != (want_r, want_out):
            bad += 1
    print(f"{path}: {len(lines)} lines, {len(lines) - bad} agree with Python's integers")

Three builds of add_n checked against Python's integers Python · wide_session.py

import pathlib
import sys

here = pathlib.Path(__file__).parent
sys.path.insert(0, str(here / "sessions"))
sys.path.insert(0, str(here))
import check_wide
import session

# Three builds of the same checker: AArch64 assembly (native), x86-64 assembly (Rosetta 2) and the RISC-V method
# written in C (native). Each writes 34 lines; the third command shows the first line, cut to 80 characters.
session.run("""
clang -O1 -o wide_a64 wide.c aarch64/add_n.s
./wide_a64 > wide_a64.txt
head -1 wide_a64.txt | cut -c1-80
clang -O1 -arch x86_64 -o wide_x64 wide.c x86_64/add_n.s
./wide_x64 > wide_x64.txt
clang -O1 -o wide_c wide.c carry.c
./wide_c > wide_c.txt
""")

# Every line checked again with Python's integers.
for name in ("wide_a64.txt", "wide_x64.txt", "wide_c.txt"):
    check_wide.check(name)

# macOS cannot run the RISC-V file: assemble it and read add_n back.
session.run("""
llvm-mc --triple=riscv64 -filetype=obj -o add_n_rv.o riscv/add_n.s
llvm-objdump -d --no-show-raw-insn --disassemble-symbols=add_n add_n_rv.o
""")

Output

$ clang -O1 -o wide_a64 wide.c aarch64/add_n.s
$ ./wide_a64 > wide_a64.txt
$ head -1 wide_a64.txt | cut -c1-80
+ 1 db9c559891948d23 78bc927ded35455d 5458e8167ec9d280 1
$ clang -O1 -arch x86_64 -o wide_x64 wide.c x86_64/add_n.s
$ ./wide_x64 > wide_x64.txt
$ clang -O1 -o wide_c wide.c carry.c
$ ./wide_c > wide_c.txt
wide_a64.txt: 34 lines, 34 agree with Python's integers
wide_x64.txt: 34 lines, 34 agree with Python's integers
wide_c.txt: 34 lines, 34 agree with Python's integers
$ llvm-mc --triple=riscv64 -filetype=obj -o add_n_rv.o riscv/add_n.s
$ llvm-objdump -d --no-show-raw-insn --disassemble-symbols=add_n add_n_rv.o

add_n_rv.o:	file format elf64-littleriscv

Disassembly of section .text:

0000000000000000 <add_n>:
       0:      	li	t0, 0x0
       4:      	beqz	a3, 0x3c <add_n+0x3c>
       8:      	ld	t1, 0x0(a1)
       c:      	ld	t2, 0x0(a2)
      10:      	add	t1, t1, t2
      14:      	sltu	t3, t1, t2
      18:      	add	t1, t1, t0
      1c:      	sltu	t4, t1, t0
      20:      	or	t0, t3, t4
      24:      	sd	t1, 0x0(a0)
      28:      	addi	a0, a0, 0x8
      2c:      	addi	a1, a1, 0x8
      30:      	addi	a2, a2, 0x8
      34:      	addi	a3, a3, -0x1
      38:      	bnez	a3, 0x8 <add_n+0x8>
      3c:      	mv	a0, t0
      40:      	ret

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 wide_session.py

All three builds agree with Python on all 34 lines: the AArch64 file, the x86-64 file through Rosetta 2, and the RISC-V method in C. The first line of the file shows its format, one-limb operands, the sum and the carry: db9c559891948d23 + 78bc927ded35455d is 5458e8167ec9d280 with a carry of 1. The last two lines are the worst case: (2⁵¹² − 1) + 1, where the carry ripples through all eight limbs and leaves as the carry out, and 1 − (2⁵¹² − 1), which borrows through all eight.

Counting the loop with add between two adc

add rax, 1 in place of inc rax writes CF, so every adc after it adds the counter’s carry, which is 0, instead of the carry of the limb below. The sum is right whenever no carry crosses a limb, so random tests often pass. Count with inc and dec, or test with operands such as 2⁵¹² − 1 and 1 that carry through every limb.

Checkpoint

Check: Loops over limbs, checked against Python

Question 1 of 2 A 256-bit number is stored as four 64-bit limbs, least significant first. Limb 3 is worth 2 to the power of what?
Type a number.
Your answer

A hint

Limb i is worth 2^(64 i).

Show the answer: Question 1 of 2

Answer: 192

Limb 0 is worth 1, limb 1 is worth 2^64, limb 2 is worth 2^128 and limb 3 is worth 2^192. The number is limb0 + limb1 × 2^64 + limb2 × 2^128 + limb3 × 2^192.
Question 2 of 2 Someone replaces inc rax with add rax, 1 in the x86-64 add_n loop. Which test fails?
Choose one answer.

Only one-limb additions Every test, because add rax, 1 changes rax by a different amount (2^512 − 1) + 1 over eight limbs: the carry is lost after the first limb None: CF and the index are independent

Show the answer: Question 2 of 2

Answer: (2^512 − 1) + 1 over eight limbs: the carry is lost after the first limb

inc leaves CF alone, which is why the loop uses it. add rax, 1 sets CF from rax + 1, 0 for any realistic index, so a carry never crosses from one limb to the next. Tests where no carry crosses a limb still pass, which is why the worst case belongs in every test suite.

A wide product is a sum of 64-bit partial products

Multiplication is where the high halves of the multiplication lesson come back. A product of two 2-limb numbers has four limbs, and every pair of limbs contributes a partial product at its own place, as every pair of digits does in long multiplication on paper. Step through it with two-digit limbs, small enough to check in your head:

Interactive · step by step Schoolbook multiplication with limbs, in base 100 Step through 1234 x 5678 with two-digit limbs. A 64-bit limb works the same way, in base 2^64 instead of base 100.

The drawing shows the whole scene; its 7 steps are listed below.

Every step as text

Numbers made of limbs. a = 1234 has limbs a1 = 12 and a0 = 34; b = 5678 has b1 = 56 and b0 = 78. Each limb is one digit in base 100, as a 64-bit limb is one digit in base 2^64.
The lowest partial product. a0 x b0 = 2652 needs two limbs. Its low limb, 52, is r0; its high limb, 26, goes one place up, to r1. On AArch64 these two halves are mul and umulh.
Two cross products. a0 x b1 = 1904 and a1 x b0 = 0936 are worth 100 times more, so each starts one limb up: their low limbs, 04 and 36, add into r1, and their high limbs, 19 and 09, into r2.
Column r1 has no carry. r1 = 26 + 04 + 36 = 66, which fits in one limb, so nothing carries into r2.
The top partial product. a1 x b1 = 0672 is worth 100^2 more than a0 x b0: its low limb, 72, adds into r2 and its high limb, 06, is r3.
Column r2 carries. r2 = 19 + 09 + 72 = 100, one more than a limb holds: r2 keeps 00 and a carry of 1 goes to r3, which becomes 06 + 1 = 07. This is where adds and adcs, or add and sltu, come in.
Four limbs of product. Read r3 to r0: 07 00 66 52, which is 7,006,652 = 1234 x 5678. Two limbs times two limbs gave four, from four partial products and the carries between columns.

With 64-bit limbs each partial product is two instructions: mul for its low half, and umulh on AArch64, mulhu on RISC-V or the one-operand mul on x86-64 for its high half. Where the partial products land decides what a function needs:

Partial product	Low half lands in	High half lands in	Needed for the low 128 bits
a0 × b0	r0	r1	both halves
a0 × b1 and a1 × b0	r1	r2	low halves only
a1 × b1	r2	r3	not at all

C’s unsigned __int128 multiplication keeps only the low 128 bits, so mul128 computes one full 64 × 64-bit product and two low halves, and adds without carries: nothing above bit 127 is kept. mul_2x2 keeps all 256 bits, so it needs all four partial products and carries between the columns, which is where adds and adcs, or add and sltu, come in:

mul128 and mul_2x2

AArch64 · aarch64/mul.s

// Wide products for AArch64.
// mul128 keeps the low 128 bits of a 128 x 128-bit product: a = x1:x0, b = x3:x2, result in x1:x0.
// mul_2x2 keeps all 256 bits of the product of two 2-limb numbers: r in x0, a in x1, b in x2, limbs low first.
.text
.p2align 2
.globl _mul128
_mul128:                    // u128 mul128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi)
    umulh x8, x0, x2        // high half of alo x blo
    madd x8, x0, x3, x8     // + low half of alo x bhi
    madd x1, x1, x2, x8     // + low half of ahi x blo: the high limb
    mul x0, x0, x2          // low half of alo x blo: the low limb
    ret
.globl _mul_2x2
_mul_2x2:                   // void mul_2x2(uint64_t r[4], const uint64_t a[2], const uint64_t b[2])
    ldp x3, x4, [x1]        // a0, a1
    ldp x5, x6, [x2]        // b0, b1
    mul x7, x3, x5          // r0 = low half of a0 x b0
    umulh x8, x3, x5        // r1 starts as the high half of a0 x b0
    mul x9, x3, x6          // a0 x b1, low and high
    umulh x10, x3, x6
    mul x11, x4, x5         // a1 x b0, low and high
    umulh x12, x4, x5
    mul x13, x4, x6         // a1 x b1, low and high
    umulh x14, x4, x6
    adds x8, x8, x9         // r1 += low of a0 x b1
    adcs x10, x10, x13      // r2 = high of a0 x b1 + low of a1 x b1 + C
    adc x14, x14, xzr       // r3 = high of a1 x b1 + C
    adds x8, x8, x11        // r1 += low of a1 x b0
    adcs x10, x10, x12      // r2 += high of a1 x b0 + C
    adc x14, x14, xzr       // r3 += C
    stp x7, x8, [x0]
    stp x10, x14, [x0, #16]
    ret

x86-64 · x86_64/mul.s

# Wide products for x86-64, in GNU as Intel syntax. The one-operand mul writes rdx:rax.
# mul128 keeps the low 128 bits of a 128 x 128-bit product: a = rsi:rdi, b = rcx:rdx, result in rdx:rax.
# mul_2x2 keeps all 256 bits of the product of two 2-limb numbers: r in rdi, a in rsi, b in rdx, limbs low first.
.intel_syntax noprefix
.text
.globl _mul128
_mul128:                    # u128 mul128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi)
    imul rsi, rdx           # low half of ahi x blo
    imul rcx, rdi           # low half of bhi x alo
    mov rax, rdi
    mul rdx                 # rdx:rax = alo x blo
    add rdx, rsi            # the high limb collects the two cross products
    add rdx, rcx
    ret
.globl _mul_2x2
_mul_2x2:                   # void mul_2x2(uint64_t r[4], const uint64_t a[2], const uint64_t b[2])
    mov r8, rdx             # r8 = b, because mul overwrites rdx
    mov rax, qword ptr [rsi]
    mul qword ptr [r8]      # a0 x b0
    mov qword ptr [rdi], rax          # r0
    mov r9, rdx                       # r1 starts as its high half
    mov rax, qword ptr [rsi]
    mul qword ptr [r8 + 8]  # a0 x b1
    add r9, rax
    adc rdx, 0
    mov r10, rdx                      # r2
    mov rax, qword ptr [rsi + 8]
    mul qword ptr [r8]      # a1 x b0
    add r9, rax
    adc r10, rdx
    setc r11b                         # the carry into r3, saved before the next mul changes CF
    movzx r11d, r11b
    mov qword ptr [rdi + 8], r9       # r1
    mov rax, qword ptr [rsi + 8]
    mul qword ptr [r8 + 8]  # a1 x b1
    add r10, rax
    adc r11, rdx
    mov qword ptr [rdi + 16], r10     # r2
    mov qword ptr [rdi + 24], r11     # r3
    ret

RISC-V · riscv/mul.s

# The full product of two 2-limb numbers for RV64IM, which has no carry flag: every carry is an sltu.
# r in a0, a in a1, b in a2, limbs low first.
.text
.globl mul_2x2
mul_2x2:                    # void mul_2x2(uint64_t r[4], const uint64_t a[2], const uint64_t b[2])
    ld t0, 0(a1)            # a0
    ld t1, 8(a1)            # a1
    ld t2, 0(a2)            # b0
    ld t3, 8(a2)            # b1
    mul t4, t0, t2          # r0 = low half of a0 x b0
    mulhu t5, t0, t2        # r1 starts as its high half
    sd t4, 0(a0)
    mul t4, t0, t3          # low half of a0 x b1
    mulhu t6, t0, t3        # r2 starts as its high half
    add t5, t5, t4
    sltu t4, t5, t4         # carry into r2
    add t6, t6, t4          # cannot carry: a high half is at most 2^64 - 2
    mul t4, t1, t2          # low half of a1 x b0
    mulhu a3, t1, t2        # its high half
    add t5, t5, t4
    sltu t4, t5, t4         # carry into r2
    sd t5, 8(a0)            # r1
    add a3, a3, t4          # cannot carry either
    add t6, t6, a3
    sltu a4, t6, a3         # carry into r3
    mul t4, t1, t3          # low half of a1 x b1
    mulhu a5, t1, t3        # its high half
    add t6, t6, t4
    sltu t4, t6, t4         # carry into r3
    add a5, a5, a4
    add a5, a5, t4
    sd t6, 16(a0)           # r2
    sd a5, 24(a0)           # r3
    ret

mul.c: mul128 against unsigned __int128, mul_2x2 for Python C · mul.c

// Checks mul128 against unsigned __int128, then prints the 256-bit products of mul_2x2 in hex, most significant
// limb first, for a checker that uses Python's integers.
#include <stdint.h>
#include <stdio.h>

typedef struct { uint64_t lo, hi; } u128;
u128 mul128(uint64_t alo, uint64_t ahi, uint64_t blo, uint64_t bhi);
void mul_2x2(uint64_t r[4], const uint64_t a[2], const uint64_t b[2]);

typedef unsigned __int128 ref128;

static void low(const char *what, ref128 a, ref128 b) {
    u128 r = mul128((uint64_t)a, (uint64_t)(a >> 64), (uint64_t)b, (uint64_t)(b >> 64));
    ref128 want = a * b;  // C keeps the low 128 bits, like mul128
    int ok = r.hi == (uint64_t)(want >> 64) && r.lo == (uint64_t)want;
    printf("%-20s hi %016llx  lo %016llx  %s\n", what, (unsigned long long)r.hi, (unsigned long long)r.lo,
           ok ? "ok" : "WRONG");
}

static void full(ref128 a, ref128 b, FILE *out) {
    uint64_t x[2] = {(uint64_t)a, (uint64_t)(a >> 64)}, y[2] = {(uint64_t)b, (uint64_t)(b >> 64)}, r[4];
    mul_2x2(r, x, y);
    fprintf(out, "%016llx%016llx %016llx%016llx %016llx%016llx%016llx%016llx\n", (unsigned long long)x[1],
            (unsigned long long)x[0], (unsigned long long)y[1], (unsigned long long)y[0], (unsigned long long)r[3],
            (unsigned long long)r[2], (unsigned long long)r[1], (unsigned long long)r[0]);
}

int main(void) {
    const ref128 two64 = (ref128)1 << 64, e19 = 10000000000000000000u, e20 = (ref128)e19 * 10;
    low("(2^64 + 1)(2^64 - 1)", two64 + 1, two64 - 1);
    low("2^127 x 2", (ref128)1 << 127, 2);
    low("10^20 x 10^19", e20, e19);

    FILE *out = fopen("products.txt", "w");
    if (!out) return 1;
    full(e20 - 1, e20 - 1, out);                                             // (10^20 - 1)^2
    full(12345678901234567890u, (ref128)9876543210987654321u * 10, out);     // the 40-digit product
    full(~(ref128)0, ~(ref128)0, out);                                       // (2^128 - 1)^2
    full(two64 + 1, two64 - 1, out);
    full((ref128)0x0123456789abcdef << 64 | 0xfedcba9876543210, (ref128)0xdeadbeefcafef00d << 64 | 0x0badc0de, out);
    return fclose(out) != 0;
}

check_products.py: each product recomputed in Python Python · check_products.py

"""Checks the 256-bit products mul_2x2 wrote to products.txt with Python's integers, and prints them in decimal."""


def short(n: int, keep: int) -> str:
    """n in decimal; longer than `keep` digits, only its first and last 10 digits, so that every line stays short."""
    s = str(n)
    return s if len(s) <= keep else f"{s[:10]}...{s[-10:]}"


def check(path: str) -> None:
    for text in open(path).read().split("\n")[:-1]:
        a, b, r = (int(x, 16) for x in text.split())
        verdict = "ok" if a * b == r else "WRONG"
        print(f"{short(a, 20)} x {short(b, 20)}")
        print(f"  = {short(r, 40)}  ({len(str(r))} digits, {verdict})")

Wide products on AArch64 and x86-64, counted on three ISAs Python · mul_session.py

import pathlib
import sys

here = pathlib.Path(__file__).parent
sys.path.insert(0, str(here / "sessions"))
sys.path.insert(0, str(here))
import check_products
import session

# mul128 checked against unsigned __int128 on AArch64; mul_2x2 writes its products to products.txt.
session.run("""
clang -O1 -o mul_a64 mul.c aarch64/mul.s
./mul_a64
""")

# Python's integers check every product and print it in decimal.
check_products.check("products.txt")

# The x86-64 build (Rosetta 2) must write the same file; then each mul_2x2 is counted, instruction by instruction.
session.run("""
cp products.txt a64.txt
clang -O1 -arch x86_64 -o mul_x64 mul.c x86_64/mul.s
./mul_x64 | tail -1
diff a64.txt products.txt && echo "x86-64 wrote the same 5 products"
clang -c -o mul_a64.o aarch64/mul.s
objdump -d --disassemble-symbols=_mul_2x2 mul_a64.o | grep -cE '^ +[0-9a-f]+:'
clang -arch x86_64 -c -o mul_x64.o x86_64/mul.s
objdump -d --disassemble-symbols=_mul_2x2 mul_x64.o | grep -cE '^ +[0-9a-f]+:'
llvm-mc --triple=riscv64 -mattr=+m -filetype=obj -o mul_rv.o riscv/mul.s
llvm-objdump -d --disassemble-symbols=mul_2x2 mul_rv.o | grep -cE '^ +[0-9a-f]+:'
""")

Output

$ clang -O1 -o mul_a64 mul.c aarch64/mul.s
$ ./mul_a64
(2^64 + 1)(2^64 - 1) hi ffffffffffffffff  lo ffffffffffffffff  ok
2^127 x 2            hi 0000000000000000  lo 0000000000000000  ok
10^20 x 10^19        hi f050fe938943acc4  lo 5f65568000000000  ok
99999999999999999999 x 99999999999999999999
  = 9999999999999999999800000000000000000001  (40 digits, ok)
12345678901234567890 x 98765432109876543210
  = 1219326311370217952237463801111263526900  (40 digits, ok)
3402823669...1768211455 x 3402823669...1768211455
  = 1157920892...9593217025  (78 digits, ok)
18446744073709551617 x 18446744073709551615
  = 340282366920938463463374607431768211455  (39 digits, ok)
1512366075...9683137040 x 2959907550...7992582366
  = 4476463765...3465436640  (75 digits, ok)
$ cp products.txt a64.txt
$ clang -O1 -arch x86_64 -o mul_x64 mul.c x86_64/mul.s
$ ./mul_x64 | tail -1
10^20 x 10^19        hi f050fe938943acc4  lo 5f65568000000000  ok
$ diff a64.txt products.txt && echo "x86-64 wrote the same 5 products"
x86-64 wrote the same 5 products
$ clang -c -o mul_a64.o aarch64/mul.s
$ objdump -d --disassemble-symbols=_mul_2x2 mul_a64.o | grep -cE '^ +[0-9a-f]+:'
19
$ clang -arch x86_64 -c -o mul_x64.o x86_64/mul.s
$ objdump -d --disassemble-symbols=_mul_2x2 mul_x64.o | grep -cE '^ +[0-9a-f]+:'
24
$ llvm-mc --triple=riscv64 -mattr=+m -filetype=obj -o mul_rv.o riscv/mul.s
$ llvm-objdump -d --disassemble-symbols=mul_2x2 mul_rv.o | grep -cE '^ +[0-9a-f]+:'
29

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 mul_session.py

mul128 matched unsigned __int128 on all three pairs, and every 256-bit product of mul_2x2 matched Python, the same on both ISAs. Two of them have 40 digits: (10²⁰ − 1)² and 12345678901234567890 × 98765432109876543210 = 1219326311370217952237463801111263526900. To check a product like that without writing a program, MySmartCoPilot’s big number calculator multiplies whole numbers of any length exactly.

The last three numbers count the instructions of mul_2x2, ret included: 19 on AArch64, 24 on x86-64 and 29 on RISC-V. Eight of AArch64’s are the multiplies themselves. x86-64 spends more on moving operands into rax and copying results out of rdx, and RISC-V spends an sltu on every carry.

Key idea

A product of two n-limb numbers is the sum of n² partial products, each a low half and a high half placed at its own limbs, with carries between the columns. Keeping only the low 128 bits drops a1 × b1 and the high halves of the cross products, which is why mul128 needs no carries.

Checkpoint

Check: Wide products from partial products

Question 1 of 2 mul128 returns the low 128 bits of a 128 × 128-bit product. Which partial product does it never compute?
Choose one answer.

a1 × b1, the high limbs times each other a0 × b1 None: it computes all four a0 × b0, the low limbs times each other

Show the answer: Question 1 of 2

Answer: a1 × b1, the high limbs times each other

a1 × b1 is multiplied by 2^64 × 2^64 = 2^128, so it changes only bits 128 and up, which mul128 discards. The cross products are worth 2^64, so only their low halves reach bits 64 to 127.
Question 2 of 2 With two-digit limbs, 9999 × 9999 has four partial products of 99 × 99 = 9801. Column r1 adds the high limb of a0 × b0 and the low limbs of the two cross products. What carries from r1 into r2?
Type a number.
Your answer

A hint

Each 9801 has limbs 98 and 01. Add 98 + 01 + 01.

Show the answer: Question 2 of 2

Answer: 1

r1 = 98 + 01 + 01 = 100, one more than a two-digit limb holds, so r1 keeps 00 and carries 1 into r2. The full product, 99 98 00 01, is 99,980,001 = 9999 × 9999.

Practise

The exercise asks for add_n and sub_n in Python on lists of 64-bit limbs, the RISC-V way: every value kept below 2⁶⁴ and every carry found with a comparison. Its sample tests use one to three limbs, including the cases where a carry or a borrow crosses every limb:

Exercise · Medium · Python

Add and subtract numbers made of 64-bit limbs

A big number is a list of 64-bit limbs, least significant first: [lo, hi] is lo + hi × 2⁶⁴. Write two Python functions that work on two such lists of the same length, the way the RISC-V add_n and sub_n of the lesson do:

add_n(a, b) returns (r, carry): r is the list of limbs of a + b, as long as a, and carry is 1 when the sum needs one more limb, else 0.
sub_n(a, b) returns (r, borrow): r is the list of limbs of a − b wrapped to the same number of limbs, and borrow is 1 when b is larger than a, else 0.

So add_n([2**64 - 1], [1]) is ([0], 1), add_n([2**64 - 1, 0], [1, 0]) is ([0, 1], 0), and sub_n([0, 1], [1, 0]) is ([2**64 - 1, 0], 0). Two empty lists give ([], 0).

Work as RISC-V must: keep every value below 2⁶⁴ with & (2**64 - 1) and find each carry or borrow with a comparison, one limb at a time, from limb 0 upwards. Do not join the limbs into one Python integer. The sample tests use one to three limbs, including carries and borrows that cross every limb.

Starter code · limbs.py

MASK = 2**64 - 1


def add_n(a, b):
    """a + b for two equal-length lists of 64-bit limbs, least significant first: return (limbs, carry)."""
    return [], 0  # replace with your code


def sub_n(a, b):
    """a - b for two equal-length lists of 64-bit limbs, least significant first: return (limbs, borrow)."""
    return [], 0  # replace with your code

The sample tests · test_limbs.py

"""Sample tests: one to three limbs, with carries and borrows that stop early and ones that cross every limb."""

from limbs import add_n, sub_n

M = 2**64 - 1  # a limb of all ones


def test_one_limb_without_a_carry():
    assert add_n([1], [2]) == ([3], 0)
    assert add_n([0], [0]) == ([0], 0)


def test_one_limb_that_carries():
    assert add_n([M], [1]) == ([0], 1)


def test_a_carry_into_the_next_limb():
    assert add_n([M, 0], [1, 0]) == ([0, 1], 0)


def test_equal_low_limbs_do_not_carry():
    assert add_n([0, 0], [5, 0]) == ([5, 0], 0)


def test_a_carry_through_every_limb():
    assert add_n([M, M, M], [1, 0, 0]) == ([0, 0, 0], 1)


def test_both_kinds_of_carry():
    assert add_n([M, 5], [1, M - 5]) == ([0, 0], 1)  # the second limb carries only because of the carry in
    assert add_n([M, M, M], [M, M, M]) == ([M - 1, M, M], 1)


def test_no_limbs():
    assert add_n([], []) == ([], 0)
    assert sub_n([], []) == ([], 0)


def test_one_limb_that_borrows():
    assert sub_n([0], [1]) == ([M], 1)
    assert sub_n([7], [7]) == ([0], 0)


def test_a_borrow_from_the_next_limb():
    assert sub_n([0, 1], [1, 0]) == ([M, 0], 0)
    assert sub_n([5, 7], [3, 2]) == ([2, 5], 0)


def test_a_borrow_through_every_limb():
    assert sub_n([0, 0, 0], [1, 0, 0]) == ([M, M, M], 1)


def test_a_larger_b_wraps_and_borrows():
    assert sub_n([3, 2], [5, 7]) == ([M - 1, M - 5], 1)


def test_three_limbs_against_whole_numbers():
    a = [0x0123456789ABCDEF, 0xFEDCBA9876543210, 0x0F0F0F0F0F0F0F0F]
    b = [0xF000000000000001, 0x0123456789ABCDEF, 0xF0F0F0F0F0F0F0F0]
    whole_a = a[0] + (a[1] << 64) + (a[2] << 128)
    whole_b = b[0] + (b[1] << 64) + (b[2] << 128)
    total = whole_a + whole_b
    assert add_n(a, b) == ([total & M, (total >> 64) & M, (total >> 128) & M], total >> 192)
    difference = (whole_a - whole_b) % 2**192
    assert sub_n(a, b) == ([difference & M, (difference >> 64) & M, difference >> 128], 1)

A hint

Loop over the limbs with zip(a, b) and keep a carry that starts at 0. For a sum, s = (x + y) & MASK carried exactly when s < y; adding the carry in, s = (s + carry) & MASK, carried exactly when s < carry; the carry out is the or of the two, and they are never both 1. For a difference, the limb borrows when x < y, or when x − y, wrapped, is below the borrow coming in.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

After the exercise, take the page’s C and assembly files to an Apple silicon Mac, or to the Linux lab of the toolchain lesson after deleting the underscore in front of each symbol:

Before you run anything, predict what add128 returns for a = b = 2¹²⁷ and what sub128 returns for 0 − 2¹²⁷. Add both lines to main in add128.c and check them with both builds.
Write mul128 for RISC-V with mulhu and three mul, following the AArch64 version, and assemble it with llvm-mc --triple=riscv64 -mattr=+m -filetype=obj to check that it is valid.
Multiply 2⁶⁴ + 1 by itself in the big number calculator, predict the four limbs mul_2x2 returns for it, then add the pair to main in mul.c and compare.

Interview questions

A warm-up for freshers: how do you add two 128-bit numbers on a CPU whose registers hold 64 bits?

Split each number into two 64-bit limbs, low and high, and add them as you would add two-digit numbers on paper: first the low limbs, then the high limbs plus the carry out of the low add. On x86-64 that is add and then adc, add with carry, which adds CF; on AArch64 it is adds, which sets C, and then adc. RISC-V has no carry flag, so it recovers the carry with a compare: after add, the wrapped low sum is below an operand exactly when the add carried, so sltu gives the carry, and two more adds put the high limbs and the carry together. For example, (2⁶⁴ − 1) + 1 gives low limb 0 with a carry, and high limb 0 + 0 + 1 = 1, which is 2⁶⁴.

This lesson also feeds two interview questions in the bank, porting a big-integer addition loop to RISC-V and designing a 256-bit product; each comes with a starting step and the follow-ups to expect:

Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.

Choose a pass

Mid to senior

A big-integer library adds numbers of n limbs with an adc loop on x86-64 and an adcs loop on AArch64. You must port it to RISC-V. What does each limb cost there and why, how do you make the port correct, and how do you test it?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Senior to staff

Design a function that returns the full 256-bit product of two 128-bit numbers on x86-64, AArch64 and RISC-V. Which partial products does it need, how do the carries flow, what does each ISA execute, and how do you test it?

Model answer, Pro. First step and follow-ups

Flashcards · 6 cards

Recall it, then check

Say the answer to yourself before you look: recalling it is what makes it stick.

How do you add two 128-bit numbers on a CPU with 64-bit registers?

Split each into a low and a high 64-bit limb and add like digits on paper: low limbs first, then the high limbs plus the carry out of the low add. (2^64 - 1) + 1 gives a low limb of 0 with a carry, and a high limb of 1.
Which instructions chain a carry or borrow from limb to limb on x86-64 and AArch64?

add then adc, and sub then sbb, on x86-64. adds then adc or adcs, and subs then sbc or sbcs, on AArch64. The borrow shows as CF = 1 on x86-64 and as C = 0 on AArch64.
RISC-V has no carry flag. How does it find the carry of s = a + b?

With a compare: the sum wrapped exactly when s is below b, so sltu s, b gives the carry. A borrow of a - b is a below b, tested before the subtract. A limb with a carry coming in needs two compares and an or.
What must a loop over limbs keep between its iterations, and how does each ISA keep it?

The carry from one limb to the next. x86-64 counts with inc and dec, which leave CF untouched; AArch64 counts with sub and cbnz, which leave the flags alone; RISC-V simply keeps the carry in a register.
How is the product of two multi-limb numbers built?

As the sum of the partial products of every pair of limbs, each with a low and a high half placed at its own limb positions, plus carries between the columns. Results are checked against unsigned __int128 and Python's integers.
Why does a function that keeps only the low 128 bits of a 128 x 128-bit product need no carries?

Everything that would need them lands above bit 127: the product of the two high limbs and the high halves of the cross products. Only the low products and the low halves of the cross terms remain.

Key takeaways

A number wider than a register is stored as limbs, and two of them are added low limb first, each next limb adding the carry the one below it produced.
x86-64 chains add with adc and sub with sbb, and AArch64 chains adds with adc or adcs and subs with sbc or sbcs, with the borrow stored as CF = 1 on x86-64 and C = 0 on AArch64.
RISC-V recovers each carry with sltu after the add, and each borrow with sltu before the subtract, so a limb with a carry in costs two compares and an or.
A loop over limbs must keep the carry between iterations: x86-64 counts with inc and dec, AArch64 with sub and cbnz, and RISC-V keeps the carry in a register.
A wide product is the sum of the partial products of every pair of limbs, low and high halves placed at their limbs with carries between the columns, and results are checked against unsigned __int128 and Python’s integers.

Terms in this lesson

carry chain: A sequence of additions or subtractions in which each step takes in the carry or borrow of the step below it: add then adc on x86-64, adds then adcs on AArch64, or add and sltu on RISC-V.
limb: One machine word of a number stored as several words, the name the GNU MP library uses: a 256-bit number on a 64-bit ISA is four 64-bit limbs, usually stored least significant first.
multi-precision integer: An integer wider than one register, stored as an array of limbs and handled by loops of word-sized instructions that pass carries from limb to limb; also called a big integer or bignum.

References

Intel 64 and IA-32 Architectures Software Developer Manuals (ADD, ADC, SUB, SBB, MUL, IMUL, INC, DEC) (Intel Corporation)
Arm A-profile A64 Instruction Set Architecture (ADDS, ADC, ADCS, SUBS, SBC, SBCS, UMULH, MADD, CBNZ) (Arm Limited)
RISC-V Ratified Specifications: RV32I base integer instruction set (overflow checks with branches) (RISC-V International)
RISC-V Ratified Specifications: the M extension for integer multiplication and division (RISC-V International)
System V Application Binary Interface, AMD64 Architecture Processor Supplement (returning of values) (x86-64 psABI project)
Procedure Call Standard for the Arm 64-bit Architecture (AAPCS64) (Arm Limited)
Using the GNU Compiler Collection: 128-bit integers (GNU Project)
GNU MP manual: nomenclature and types (limbs) (GNU Project)
The Python Standard Library: numeric types int, float, complex (Python Software Foundation)
About the Rosetta translation environment (Apple Inc.)

Report a problem with this lesson

In this module: Arithmetic, logic and flags

Addition, subtraction and multiplication Free lesson, Pro answers: 20 minutes
Division: traps, defined results, remainders Free lesson, Pro answers: 20 minutes
Bitwise logic, shifts and rotates Free lesson, Pro answers: 20 minutes
Flags and condition codes Free lesson, Pro answers: 25 minutes
Carries and 128-bit arithmetic Free lesson, Pro answers: 25 minutes
Bit-manipulation instructions and extensions Free lesson, Pro answers: 25 minutes

Your country

Carries and 128-bit arithmetic

What you will learn

Before you start

What you will learn

Before you start

A 128-bit sum is two adds joined by the carry

RISC-V finds each carry with a compare

Numbers of any width are loops over limbs

A wide product is a sum of 64-bit partial products

Practise

Add and subtract numbers made of 64-bit limbs

Results of the sample tests

Interview questions

A big-integer library adds numbers of n limbs with an adc loop on x86-64 and an adcs loop on AArch64. You must port it to RISC-V. What does each limb cost there and why, how do you make the port correct, and how do you test it?

Design a function that returns the full 256-bit product of two 128-bit numbers on x86-64, AArch64 and RISC-V. Which partial products does it need, how do the carries flow, what does each ISA execute, and how do you test it?

Key takeaways

References