Sunday, October 17, 2010

LCG mod 65537

This can be done with a trick described in Knuth's TAoCP Volume 2, section 3.2.1.1.  As such:

1783:0200 52            PUSH    DX
1783:0201 B80100        MOV     AX,0001
1783:0204 BA399E        MOV     DX,9E39
1783:0207 09C0          OR      AX,AX
1783:0209 7402          JZ      020D
1783:020B F7E2          MUL     DX
1783:020D 29D0          SUB     AX,DX
1783:020F 7301          JNB     0212
1783:0211 40            INC     AX
1783:0212 A30202        MOV     [0202],AX
1783:0215 5A            POP     DX
1783:0216 C3            RET


65536 gets mapped to 0 in this case, hence the check at 207h. skipping the mul simulates the result we would get if we multiplied by 65536.

No comments: