Chapter 9 Further Reading: Arithmetic and Logic

Primary References

Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2 The per-instruction reference. Look up ADD, IMUL, DIV, ADC, SAR, etc. Pay attention to the "Flags Affected" section for each instruction — it is the authoritative record of which flags each instruction modifies. The "Operation" pseudocode section for IMUL (three forms with different flag behavior) and for DIV (the exception conditions) is particularly important.

"Hacker's Delight" by Henry S. Warren, Jr. (2nd edition) Addison-Wesley, 2012. ISBN: 0321842685. The essential reference for bit manipulation and integer arithmetic algorithms. Chapters 2-5 cover constant-time bit operations, population count, bit scanning, and division by constants. Warren's code examples are in C with assembly annotations. Chapter 10 covers integer division by constants using the multiply-by-reciprocal technique that compilers use to eliminate DIV instructions.

"The Art of 64-bit Assembly Language" by Randall Hyde No Starch Press, 2021. Chapters on arithmetic and logic cover the x86-64 instruction set with extensive examples. The flag behavior tables in Chapter 6 are particularly useful.

Multi-Precision Arithmetic

GMP (GNU Multiple Precision) Source Code gmplib.org — the mpn/x86_64/ directory contains highly optimized assembly implementations of multi-precision add, subtract, multiply, and divide. The adc chain pattern shown in Case Study 9.1 is the core of the mpn_add_n function. Studying this code shows production-quality use of MULX and ADC chaining.

"Handbook of Applied Cryptography," Chapter 14: Efficient Implementation Menezes, van Oorschot, Vanstone. Free at cacr.math.uwaterloo.ca/hac/ The standard reference for multi-precision arithmetic algorithms used in cryptography. Chapter 14 covers Montgomery multiplication, Barrett reduction, and other techniques that build on the ADC/SBB chain foundation.

Constant-Time Programming

"ctgrind" and "ct-verif" tools Tools for verifying constant-time properties of cryptographic code. The ctgrind tool (GitHub: agl/ctgrind) uses Valgrind to taint-track secret data and report when it influences branching. Essential for validating the security of constant-time implementations.

"Towards Verified, Constant-Time Floating Point Operations" — IACR ePrint 2018 Discusses the challenge of writing constant-time code in the presence of compiler optimization. Shows specific cases where GCC transforms constant-time C into variable-time assembly. Argues for assembly-level implementations for security-critical code.

OpenSSL crypto/mem.c and crypto/bn/bn_lib.c github.com/openssl/openssl The production implementations of CRYPTO_memcmp (constant-time comparison) and big-number arithmetic. The bn_lib code uses ADC chains for multi-precision arithmetic. Examining these with objdump at -O2 shows exactly how the compiler treats these patterns.

Division by Constants

"Division by Invariant Integers using Multiplication" — Torbjörn Granlund and Peter L. Montgomery ACM SIGPLAN Notices, 1994. The original paper describing the compiler technique of replacing integer division by a constant with a multiply + shift sequence. The GCC implementation in optabs.c is based directly on this paper.

LLVM's SelectionDAGTargetInfo for Division The LLVM source tree's lib/CodeGen/SelectionDAG/ contains the magic number computation code. Reading the code alongside the Granlund-Montgomery paper shows exactly how compilers decide when to use IMUL vs. LEA for constant multiplications and divisions.