Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #18029

Re: Skybuck's Parallel Static Huffman Decoding Algorithm

Show all headers | View raw

(groups reduced to jsut c.arch)
glen herrmannsfeldt wrote:
> The VAX instruction format was designed to efficiently use the
> bits, in a way somewhat similar to the way Huffman does.
> Instructions can have from one up to some high number of bytes,
> maybe 16 or so. It is not easy to figure out how many, either.
> That is one reason that VAX didn't last longer than it did.
>
> In contrast, the S/360 (and successor) instruction length is
> known from the first two bits of the opcode. Not quite as easy
> as with only one length (most RISC) but pretty easy.
>
> So, yes, if the length can be determined from a small number of
> bits in the beginning, then it isn't hard to do in parallel.

One of my early decoders had very skewed input, i.e. there was many very 
short huffman tokens and a sparse tail of much longer ones.

My decoder would simply grab N bits, where N was selected to require a 
reasonably sized lookup table, then from the table it would fetch either 
the (negative) index of a secondary table (for tokens longer than N, 
very rare), or an index into a byte-packed list of (length/tokens/bits).

The next step would simply grab the length and do a REP MOVSB to copy as 
many output tokens as indicated, then grab one more byte which specified 
how many bits to remove from the input buffer variable:

Effectively branchless, averaging ~3 decoded tokens per iteration, 
something like this:

next:
   mov eax,edx		; 11 to 32 input bits
   and eax,2047		; 11-bit lookup table
   movsx eax,word ptr token_lookup[eax*2] ;; 16 bit entries

   lea esi,token_stream[eax+1] ; Point at token list
   movzx ecx, byte ptr [esi-1]
    jcxz use_secondary_table

   rep movsb		; Copy the output tokens!
   movzx ecx,byte ptr [esi] ; How many bits did we consume?
   shr edx,cl
   sub ebx,ecx		; Buffer bits - 11
    jae next

; Refill the input buffer, there is room for at least 21 more bits!
   mov esi,[input_ptr]
   lea ecx,[ebx+11]	; Current buffer size in bits
   mov eax,[esi]		; Usually misaligned...
   shl eax,cl
   or edx,eax		; Merge the new bits into the EDX buffer

   ; Calculate how many bytes/bits to advance:
   mov eax,32
   sub eax,ecx		; Room for this many new bits
   shr eax,3		; # of input bytes accepted
   add esi,eax
   lea ebx,[ebx+eax*8]	; Adjust bit count!
   mov [input_buffer],esi
    jmp next

use_secondary_table:
   mov esi,[esi]
   shr edx,11
   sub ebx,11

; Pick up table size, lookup mask etc from this secondary table
;...

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 06:37 +0200
  Re: Skybuck's Parallel Static Huffman Decoding Algorithm glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-09-12 05:54 +0000
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm Terje Mathisen <"terje.mathisen at tmsw.no"> - 2013-09-12 10:03 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 16:28 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm Dombo <dombo@disposable.invalid> - 2013-09-14 14:57 +0200
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm Willem <willem@turtle.stack.nl> - 2013-09-14 19:12 +0000
  Re: Skybuck's Parallel Static Huffman Decoding Algorithm Jasen Betts <jasen@xnet.co.nz> - 2013-09-12 13:31 +0000
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 16:30 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm BGB <cr88192@hotmail.com> - 2013-09-12 19:39 -0500
      Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2013-09-13 08:05 +0200
        Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) BGB <cr88192@hotmail.com> - 2013-09-14 00:43 -0500
          Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-15 18:28 +0200
            Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) BGB <cr88192@hotmail.com> - 2013-09-16 17:00 -0500
              Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-26 14:37 +0200
                Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) BGB <cr88192@hotmail.com> - 2013-09-26 23:50 -0500
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Shaun" <stereobuff07@gmail.com> - 2013-09-19 04:26 -0500
        Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-22 03:25 +0200
  Re: Skybuck's Parallel Static Huffman Decoding Algorithm Thomas Richter <thor@math.tu-berlin.de> - 2013-09-21 10:09 +0200
  Re: Skybuck's Parallel Static Huffman Decoding Algorithm MitchAlsup <MitchAlsup@aol.com> - 2013-10-06 17:09 -0700

csiph-web