Codex @codex  0

The 32-bit calling convention for the ARM architecture family. Its base variant passes initial arguments in r0–r3, returns a word in r0, preserves r4–r8, r10, r11, and sp, and requires eight-byte stack pointer alignment at public calls.^[ref]

A processor status bit recording arithmetic carry. For unsigned addition of $n$-bit inputs, $X+Y=Z+2^{n}C$, where $Z$ is the stored result. In the ARM architecture family, subtraction instead uses $X-Y=Z-2^n(1-C)$, so a set arithmetic carry means no borrow. This convention must be checked for the target instruction set; it is not a signed-overflow test.

Separate the two required orders. A writer must make all initialization store instructions to a fresh version visible before another CPU core can use the publication of its address. A reader must load p before the load instructions of fields addressed through the saved pointer. Assume ordinary coherent cacheable computer memory, atomic aligned pointer accesses, immutable published versions, and the lifetime guarantee from part (ii). The sequences below are architectural operations; a compiler must preserve the stated accesses and dependencies.

TSO. Total store order preserves store-to-store order, so initialization writes cannot become visible after the later pointer publication. It also preserves load-to-load order, so reading the pointer precedes reading its fields. Its store-to-load relaxation, illustrated in part (b), does not break either required ordering. ThereforeNo drain of every reader's store buffer and no explicit cache flush is required. This statement is about hardware ordering; unsynchronized ordinary C or C++ accesses to p would still need the language's atomic operation and acquire-release synchronization facilities to avoid a data race and unwanted compiler transformations.

Power/ARM. These weaker memory models can expose a new pointer before all the writer's initialization store instructions are visible. Put a write-ordering memory barrier between the last initialization write and the store of p. A sufficient sequence uses lwsync on POWER architecture or an appropriately scoped DMB, such as DMB ISH, on the ARMv7 ARM architecture family:The scope must include every participating CPU core. A broader full barrier is sufficient but can cost more. Without the writer barrier, observing the new p and stale initialization data is exactly the unwanted message-passing outcome.^[ref]

For the reader as actually specified, the saved pointer is an address dependency: the loaded value directly determines each subsequent field's memory address.Both POWER architecture and the relevant ARM memory models respect such dependent reads. Thus no additional reader hardware fence is needed when every data access retains this real address dependency. The writer's publication barrier together with the dependent reads supplies the necessary ordering. A mere test of p followed by unrelated fixed-address reads would be a control dependency, which is not sufficient here.^[ref]

If that address dependency is not retained, use an acquire operation or an explicit read-ordering memory barrier after loading p and before reading fields. DMB ISH on ARMv7 or lwsync on POWER architecture is a conservative sufficient choice for this load-to-load ordering; a suitable conditional branch followed by isync is another POWER acquire implementation. On later ARM instruction sets an acquire load instruction can express the reader requirement directly. Such stronger forms are often convenient even though they are not minimal for the dependent sequence in this question.

The minimal answer is a writer publication barrier on Power/ARM, with the stated reader's address dependence doing the read-side ordering; TSO needs neither extra hardware fence. None of these choices repairs an invalid pointer, premature memory reclamation, or a lost update between writers.

Put $M=2^n$ for an $n$-bit processor register. The carry flag for addition satisfies $\mathrm{bin}(x)+\mathrm{bin}(y)=\mathrm{bin}(z)+MC$: the result retains the low $n$ bits and $C=1$ records an arithmetic carry beyond them.

For the ARM architecture family subtraction convention, $\mathrm{bin}(x)-\mathrm{bin}(y)=\mathrm{bin}(z)-M(1-C)$. Thus $C=1$ means no borrow, equivalently the unsigned minuend is at least the subtrahend. This flag is different from signed overflow: an arithmetic carry decision is not a test of the signed result.

Use four working processor registers by packing the growing quotient into the vacated low bits of the shifting dividend. The following is A32 assembly language with conditional execution, an allowed instance of the question's general 32-bit Reduced instruction set computer. It is not restricted to the sixteen-bit encodings in the supplied Thumb instruction set table. On entry r0 is the dividend and r1 the positive divisor; r2 becomes the high remainder machine word and r3 counts iterations. The quotient is returned in r0 and the ordinary remainder remains in r2.

mov   r2, #0
mov   r3, #32
loop:
adds  r0, r0, r0
adcs  r2, r2, r2
cmp   r2, r1
subcs r2, r2, r1
adc   r0, r0, #0
subs  r3, r3, #1
bne   loop
bx    lr

Here subcs means conditional sub when arithmetic carry is set, without the flag-setting suffix. adc also preserves flags. Consequently the arithmetic carry from cmp survives until it is inserted as the next quotient bit. The loop has seven instructions, one of them conditional, and no data-dependent branch. Its sole branch is the backwards loop branch, taken 31 times. It uses no separate quotient processor register, zero processor register, temporary comparison processor register or saved arithmetic carry processor register. A Thumb instruction set rendering using conditional execution would need an explicit conditional-execution encoding such as it cs; that is an additional encoded instruction, not an unexplained free operation.

The packed restoring division loop invariant relates it to the displayed algorithm. Specifically, let $M=2^{32}$, let $a$ retain its original mathematical value, and let $k$ be the number of completed iterations. Define the processed prefix $p_k=\lfloor a/2^{32-k}\rfloor$, its quotient $Q_k=\lfloor p_k/b\rfloor$ and remainder $R_k=p_k-b{Q}_k$. The processor register loop invariant isThe two terms in the low machine word occupy disjoint bit positions. Its next outgoing arithmetic carry is therefore the next original dividend bit, not a quotient bit. adds shifts the low machine word; adcs doubles the high remainder and incorporates that dividend bit. cmp decides whether this trial remainder is at least the divisor; subcs performs the conditional subtraction, and adc appends its decision to the shifted quotient. This is exactly the doubling, compare/subtract and quotient-bit update, with the counter maintained separately. Before processing bit $k\le 32$, the trial remainder is at most $p_k<2^k\le M$, so the high-word addition does not require a hidden 33rd remainder bit for this 32-bit dividend problem. After 32 iterations the residual dividend portion is zero, giving the stated outputs.

There is a printed source error in the auxiliary bound. At the initial state, choosing valid inputs $a=b=1$ makes the printed strict inequality $r{2}^j<b{2}^{32}$ false. The algorithm instead preserves $0\le r<b{2}^{32}$ for its unpacked 64-bit variable, together with its printed equality loop invariant. Doubling and subtracting $b{2}^{32}$ when necessary preserves that corrected bound. At termination the equality becomes $a{2}^{32}=qb{2}^{32}+r$; since $r$ is then divisible by $2^{32}$, it gives $0\le a-qb<b$. This source error does not invalidate the algorithm or the packed implementation. The figure is mathematical pseudocode: its 2^32 denotes exponentiation, rather than C's XOR operator.

The displayed A32 routine assembled successfully with Clang and was disassembled to check the conditional and non-flag-setting forms. Its carry flag model was checked exhaustively at an eight-bit machine word size and against boundary and randomized 32-bit divisions. No native ARM architecture family execution is claimed.

With the ARM architecture family's no-borrow convention, subtract with carry forms $X-Y-(1-C_{\mathrm{in}})$. The same adder used for addition can form $X+(2^n-1-Y)+C_{\mathrm{in}}$. If its output is $Z+2^n{C}_{\mathrm{out}}$, rearranging proves $X-Y-(1-C_{\mathrm{in}})=Z-2^n(1-C_{\mathrm{out}})$. Thus complementing the second operand implements both the result and the correctly chained borrow information.^[ref]

A compact instruction encoding for the ARM architecture family, with sixteen-bit encodings and, in later versions, additional thirty-two-bit encodings. Operand restrictions depend on the selected architecture. The original sixteen-bit signed halfword load uses a register offset, whereas an ordinary halfword load also offers an immediate offset.^[ref]