[Libre-soc-isa] [Bug 933] prefix-code (like huffman code) decode/encode instructions

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=933

--- Comment #8 from Jacob Lifshay <programmerjake at gmail.com> ---
rather than having RS and RC be input bit position, it might be better to have
them be whatever input bits were left over from decoding, encoded like so:

0b000...0001iiiii...iii where i is an input bit. input is taken from the lsb
and the register is shifted down. one of the CR0 bits (lt?) can be set to if
the instruction used RB or not. doing this allows easier decoding of input
streams since it doesn't need extra instructions to shift and merge the next
bytes of the input stream. if RB is r0, then it just won't take any input bits
from RB -- useful for decoding the last few bits of input.

before:
# input in memory at 8(r3), tree in r4, output in memory at 8(r5)
ldu r8, 8(r3)
li r7, 0
loop:
pcdec r6, r4, r8, r7
bso large_code  # encountered code larger than 6 bits
beq fill
stdu r6, 8(r5)
b loop
fill:
# whole bunch of complex stuff to take leftover bits in r6, merge new bits in,
update r3 and r7
# i don't want to write it out, it'd be like 8-10 instructions
b loop
# ^ main loop -- large and complex

large_code:
beq skip
stdu r6, 8(r5)
skip:
srd r6, r6, r7
# more complex stuff...


after -- much simpler:
# input in memory at 8(r3), tree in r4, output in memory at 8(r5)
li r7, 1  # 00001 -- no input bits in r7
fill:
ldu r8, 8(r3)
loop:
pcdec r6, r4, r8, r7
bso large_code  # encountered code larger than 6 bits
stdu r6, 8(r5)
blt fill
b loop
# ^ main loop -- really simple

large_code:
beq skip_store  # anything already decoded?
stdu r6, 8(r5)
skip_store:
blt skip_fill
ldu r8, 8(r3)
skip_fill:
# lets assume the longest possible code word is 16 bits like jpeg
cntlzd r9, r7
li r10, 1
sldi r10, r10, 63  # r10 = 1 << 63
srad r10, r10, r9
andc r7, r7, r10
and r10, r8, r10
or r7, r7, r10
# i'm feeling lazy, won't write out all of skip_fill right now, it's the slow
cold path anyway

-- 
You are receiving this mail because:
You are on the CC list for the bug.