The Shift Table

Using, learning, programming and modding the Gigatron and anything related.
Forum rules
Be nice. No drama.
Post Reply
qwertyface
Posts: 22
Joined: 16 Jul 2019, 09:19

The Shift Table

Post by qwertyface »

I've just started trying to implement arbitrary left and right bit shifts - I need to be able to shift 16 bit quantities by up to 15 places.

This led to me looking at the right shift table in page 5 of the ROM. I think I understand how to use it (although I think doing so would require fitting my own code in page 6). But what I don't get is how it works. Marcel's code is as follows:

Code: Select all

# Lookup table for i>>n, with n in 1..6
# Indexing ix = i & ~b | (b-1), where b = 1<<(n-1)
#       ...
#       ld   <.ret
#       st   [vTmp]
#       ld   >shiftTable,y
#       <calculate ix>
#       jmp  y,ac
#       bra  $ff
# .ret: ...
#
# i >> 7 can be always be done with RAM: [i&128]
#       ...
#       anda $80,x
#       ld   [x]
#       ...

label('shiftTable')
shiftTable = pc()

for ix in range(255):
  for n in range(1,7): # Find first zero
    if ~ix & (1 << (n-1)):
      break
  pattern = ['x' if i<n else '1' if ix&(1<<i) else '0' for i in range(8)]
  ld(ix>>n); C('0b%s >> %d' % (''.join(reversed(pattern)), n))
This results in this in the listing:

Code: Select all

shiftTable:   0500 0000  ld   $00         ;0b0000000x >> 1
              0501 0000  ld   $00         ;0b000000xx >> 2
              0502 0001  ld   $01         ;0b0000001x >> 1
              0503 0000  ld   $00         ;0b00000xxx >> 3
              0504 0002  ld   $02         ;0b0000010x >> 1
              0505 0001  ld   $01         ;0b000001xx >> 2
              0506 0003  ld   $03         ;0b0000011x >> 1
              0507 0000  ld   $00         ;0b0000xxxx >> 4
              0508 0004  ld   $04         ;0b0000100x >> 1
              0509 0002  ld   $02         ;0b000010xx >> 2
              050a 0005  ld   $05         ;0b0000101x >> 1
              050b 0001  ld   $01         ;0b00001xxx >> 3
              050c 0006  ld   $06         ;0b0000110x >> 1
              050d 0003  ld   $03         ;0b000011xx >> 2
              050e 0007  ld   $07         ;0b0000111x >> 1
 ...             
 

Is this a well known technique? Why does it work? It seems very mysterious to me!
at67
Posts: 222
Joined: 14 May 2018, 08:29

Re: The Shift Table

Post by at67 »

qwertyface wrote: 27 Nov 2020, 17:36 This led to me looking at the right shift table in page 5 of the ROM. I think I understand how to use it (although I think doing so would require fitting my own code in page 6). But what I don't get is how it works. Marcel's code is as follows:
Is this a well known technique? Why does it work? It seems very mysterious to me!
This is using the branch/jump delay slot caused by the instruction pipeline to allow random access to the ROM, i.e. as a look up table. Marcel does this everywhere throughout the firmware and a whole bunch of instructions and SYS commands rely on this delay slot feature to provide their functionality, e.g. LUP, SYS_LSRW1_48 etc.

The right shift algorithm basically uses each byte of the 16 bit word as an index into a LUT and fetches the correct byte based on the index and the right shift amount.

Check this thread out for some resources as to how the delay slot allows this functionality to work:
viewtopic.php?f=4&t=177

Also if you really want to get a simple and clear picture as to how this works, compile the following piece of gtBASIC code in my emulator/compiler and then native code single step through it and you will see how the delay slot following a branch/jump is executed before the branch/jump is taken.

Code: Select all

_runtimePath_ "../runtime"
_codeRomType_ ROMv1

cls

value = &h0080
gosub rshift1
print value

rshift1:
    asm
_breakpoint_    
        LDWI    SYS_LSRW1_48
        STW     giga_sysFn
        LDW     _value
        SYS     48
        STW     _value
    endasm
return
P.S. You would do the following to single step the native code.

Code: Select all

- save the above code as 'blah.gbas'
- run my emulator and hit 'CTRL + B'
- find 'blah.gbas' and then execute it by left clicking on it, (it will break in the vCPU code).
- hit 'CTRL + M'
- left click on the 'ROM: <xxxx>' address, (it should turn green), edit it to $0600
- left click on the 'nop' instruction at $0600, this will add a native code breakpoint
- hit 'CTRL- F7' this will run the native code emulation to $0600 and break
- single step from then on using 'CTRL-F8' and you will see how it all works
- 'CTRL - H' brings up the help
qwertyface
Posts: 22
Joined: 16 Jul 2019, 09:19

Re: The Shift Table

Post by qwertyface »

Thanks at67 - but I really meant how is the lookup table constructed. I think I partly get it: For a shift of 6 places, there are only two of the original bits in the result, so it only needs 2²=4 rows in the table. For 5 places there 3 bits, so 8 rows, and so on, up to shifts of 1 bit, which have 7 of the original bits, so 128 possible results. So there are 128+64+32+16+8+4=252 values you might want - so it all fits with space to spare.

What I'm still not completely clear on is how the formula ensures that they're interleaved and none of them land on top of each other. It's clear from the output that every second row is a shift by 1, but the others aren't so obvious to me.
qwertyface
Posts: 22
Joined: 16 Jul 2019, 09:19

Re: The Shift Table

Post by qwertyface »

I think I get it now. The effect of the formula is to set the first "insignificant" bit to a 0, and all the bits below to 1. So shifts by 1 all get indexes of the form xxxxxxx0. Shifts by two get indexes of the form xxxxxx01, and shifts by three get indexes of the form xxxxx011.

This means longer shifts can never get the same index as a shorter shift, because the shorter shift would always have a zero where the longer shift has a one.

The consequence is that shifts by 1 are all at indexes that are multiples of two (because they end in zero), shifts by two are all at indexes of the form 4n+1, shifts by three are at indexes 8n+3 and so on.

Very clever! Marcel's code still has a lot to teach me!
at67
Posts: 222
Joined: 14 May 2018, 08:29

Re: The Shift Table

Post by at67 »

I've been studying Marcel's firmware for 2.5 years on and off and it never ceases to amaze me how much complexity he is able to stuff into so few instructions.
Post Reply