Several--well 4--people have asked me off-list how the assembly-time
construction of the table of one-bit counts can be automated. Its manual
construction by inspection is possible, though not I think advisable, for a
table of the one-bit element counts for 0(1)255, which contains only 256
values. For a table of these counts for 0(1)65535, which contains 65536
values, something else is required. I have stripped a macro definition of
bullet proofing, optimization, and the like with the result
macro
ONEBITSK &loGBLAid=, --identifier, low input value
*
&hiGBLAid=, --identifier, high input value
*
&bkGBLAaid= --identifier, one-bits count GBLAa
.*
.*
.* counts the number of bits in each of the twos-complement binary
.* fullword values &(&loGBLAid), &(&loGBLAid)+1, . . . , &(&hiGBLAid)
.* and sets the successive elements of the array &(&bkGBLAaid)(1)
.* equal to these count values. For example, for
.*
.* |&idlo setc '__low__bound' --low-bound identifier
.* | gbla &(&idlo) --declare low-bound global
.* |&(&idlo) seta 0 --initialize it
.* |&idhi setc '__high_bound' --high-bound identifier
.* | gbla &(&idhi) --declare high-bound global
.* |&(&idhi) seta 7 --initialize it
.* |&o1aid setc '__out_n1bits' --identifier, output array
.* | gbla &(&o1aid)(1) --declare output array
.* | ONEBITSK loGBLAid=&idlo,hiGBLAid=&idhi,
*
.* | bkGBLAaid=&o1aid
.*
.* it sets
.*
.* &(&olaid)(1) equal to 0 because '0000' contains 0 one bits
.* &(&olaid)(2) equal to 1 because '0001' contains 1 one bit
.* &(&olaid)(3) equal to 1 because '0010' contains 1 one bit
.* &(&olaid)(4) equal to 2 because '0011' contains 2 one bits
.* &(&olaid)(5) equal to 1 because '0100' contains 1 one bit
.* &(&olaid)(6) equal to 2 because '0101' contains 2 one bits
.* &(&olaid)(7) equal to 2 because '0110' contains 2 one bits
.* &(&olaid)(8) equal to 3 because '0111' contains 3 one bits
.*
gbla &(&loGBLAid) --low-bound global
gbla &(&hiGBLAid) --high-bound global
gbla &(&bkGBLAaid)(1) --bit-counts global array
&subscript_bias seta &(&loGBLAid)-1 --one-origin subscript bias
&i seta &(&loGBLAid) --initialize element_loop subscript
.element_loop anop , --top of element_loop
&i seta &i+1 --increment element_loop index
&eoi setb (&i gt &(&hiGBLAid)) --end of interval reached?
aif (&eoi).element_lend --if so, leave element_loop
&bitchars setc A2B(&i) --BIF gets c/s representation of bits
&one_bit_counter seta 0 --initialize one-bits counter
&j seta 0 --initialize bits_loop index
.bits_loop anop , --top of bits_loop
&j seta &j+1 --increment bits_loop index
&eos setb (&j gt 32) --bit characters exhausted?
aif (&eos).bits_lend --if so, leave bits_loop
&one_bit setb ('&bitchars'(&j,1) eq '1') --is it a one bit?
&one_bit_counter seta &one_bit_counter+&one_bit --increment by 0|1
ago .bits_loop --next bit position da capo
.bits_lend anop , --bottom of bits_loop
&k seta &i-&subscript_bias --one-origin output-array subscript
&(&bkGBLAaid)(&k) seta &one_bit_counter --stow one-bits count
ago .element_loop --next element da capo
.element_lend anop , --bottom of element_loop
mexit , --macro-expanded exit
mend
This macro is "very inefficient", but notional compile-time inefficiency is a
small price to pay for ensuring that a generated execution-time table is
correct. Readers who are unfamiliar with created set symbols will find it
opaque but not unintelligible. It is also an illustration of macro of the sort
that mathematicians call a lemma: it is of no independent interest, and it does
not itself generate code. Its function is instead to facilitate and simplify
the work of another macro or macros that do generate code.
John Gilmore Ashland, MA 01721-1817 USA
