cc100aa@prism.gatech.EDU (Ray Spalding) (04/04/90)
In article <188@csinc.UUCP> rpeglar@csinc.UUCP (Rob Peglar) writes: >In article <7562@hydra.gatech.EDU>, cc100aa@prism.gatech.EDU (Ray Spalding) writes: >> >> + SA1 A1+B1 >> BX6 X1-X0 >> NZ X6,* > >This sure is classic. For those of you paying attention, notice two things: >1. The '+' sign to force word alignment in COMPASS. >2. The possibility of a mode-out on this code segment. > * If CM doesn't contain (X0) from (A1+B1) until FL, you're hosed. > This loop depends on a word matching the contents of X0 to > terminate. A classic, alright - classic bad COMPASS. I left the setup and boundary conditions as an exercise for the reader. The code appears in the routine "EQS - Equality Search Table" in COMCMTM by Greg Mansfield (the software equivalent of Seymour?). The trick is that managed tables are always one word longer than needed to hold the data. On entry to EQS, what you're searching for is stored in that extra word at the end, guaranteeing you'll find it there if not somewhere in the data first. When the loop terminates, you check the address of the found data versus the address of the end of the data + 1 (a good place for that old Aj-Bk "mode"). I believe this technique is described in Knuth's "Searching and Sorting" volume. (I'm packed up to move or I'd look it up). As someone quite properly pointed out, the loop finds the ones complement of the target also, and is therefore not completely general. But, when you know something about the data (e.g., all > 0, or all ending in a number of zero bits, or all beginning with an alphabetic), it's difficult for Greg and myself to resist it. -- Ray Spalding, Office of Computing Services Georgia Institute of Technology, Atlanta Georgia, 30332-0275 uucp: ...!{allegra,amd,hplabs,ut-ngp}!gatech!prism!cc100aa Internet: cc100aa@prism.gatech.edu
tdonahue@prost.bbn.com (Tim Donahue) (04/14/90)
In article <27675@ut-emx.UUCP>, kjm@ut-emx writes: >In article <28567@cup.portal.com>, Tim_N_Roberts@cup.portal.com writes: >> I can't believe people are complaining about the inclusion of >> SAi Aj+Bk >> in the instruction set, but no one has said ANYTHING about population count! >> If ever an instruction called out to be replaced, it was CXi Xj. > >Speak for yourself! Pop-count was, at minimum, good for fixing the >"negative zero" problem. It could also be used to good advantage in >other situations in dealing with bit vectors. > How so? > >Kenneth J. Montgomery Senior Operating System Specialist Cheers, Tim