SIB: The Byte That Exists Because rsp Is Special

$ cd courses/isa/assets/samples
$ ./build_samples.sh 2>&1 | sed -n '/I4/,/I5/p'
$ python3 x86dec.py --why 8b 04 25 11 22 33 44
$ python3 crosscheck.py 2>&1 | sed -n '/^I4/,/^I5/p'

  1. Write a SIB decomposer and run it over all
     256 values, printing scale, index and base:

       for sib in range(256):
           ss, ix, bs = sib >> 6, (sib >> 3) & 7, sib & 7
           print(sib, 1 << ss, ix, bs)

     Now annotate each of the 256 with what it
     actually means, treating index=100 and
     base=101 as special. How many distinct
     address FORMS are there in total?

     (Fewer than 256, because ss is a scale not an
     address component: 4 scales x 8 indices x
     8 bases, minus the two special values, plus
     the two "no base" cases. Count them -- the
     answer is around 240, which is the point:
     the byte is nearly injective and was designed
     to be.)

  2. Find the rbp gap empirically. Try to encode
     [rbp+rsi*1] with no displacement and show
     that you cannot:

       # mod=00 rm=101 is RIP-relative, not rbp
       # mod=00 rm=100 + SIB base=101 is absolute
       # so rbp at mod=00 with no disp is unreachable

     Then write the smallest thing that IS
     reachable and check it:

       8b 44 25 00   mov eax,[rbp+riz*1+0x0]

     (One wasted byte. Then compile a function
     with a frame pointer and count the zero
     displacements clang emits -- that is the
     price, measured on real code rather than
     argued from the spec.)

  3. Now the dependency. Write a length function
     that uses ONLY the ModRM, and run it over
     every SIB byte at mod=00. Count the failures:

       for sib in range(256):
         bs = bytes([0x8b, 0x04, sib]) + disp4
         ...

     (32 failures: every SIB with base=101. The
     ModRM said mod=00 so no displacement, and the
     SIB said otherwise. A decoder must read both
     before it can size the instruction, and there
     is no shortcut.)

  4. Test the scale field against reality. Compile
     the same loop four ways and find the SIB byte
     in each:

       for s in 1 2 4 8; do
         printf 'int f(char*a,long i){return a[i*%d];}\n' $s
       done

     (Expect *1, *2 and *4 to use the SIB scale
     field directly, and *8 to need a shift or an
     lea. The scale field tops out at 8, and finding
     where the hardware stops helping is more
     informative than confirming where it starts.)

  5. Finally, the experiment that makes the SIB
     legible: count SIB bytes in real code and
     correlate with what the source was doing.

       objdump -d /bin/ls | grep -c 'rsp\*'
       objdump -d /bin/ls | grep -oE '\((%r[a-z0-9]+),%r[a-z0-9]+(,[124])?\)' \
         | sort | uniq -c | sort -rn | head -20

     The top patterns will be dominated by [rsp]
     and [rsp+N] with scale 1 -- which is stack
     traffic, and stack traffic is [rsp] because
     rsp IS the stack. Then look for the rare
     scaled forms and read the surrounding code:
     they are array indexing, and they are rarer
     than you would expect from reading C, which
     is itself the finding from step 4 -- most
     array access in compiled code is a pointer
     that was already advanced, not an index that
     is being scaled.