Groups > comp.compression > #2023

Re: Skybuck's Parallel Static Huffman Decoding Algorithm

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.stack.nl!.POSTED!not-for-mail
From	Willem <willem@turtle.stack.nl>
Newsgroups	alt.comp.lang.c, comp.arch, comp.compression
Subject	Re: Skybuck's Parallel Static Huffman Decoding Algorithm
Date	Sat, 14 Sep 2013 19:12:01 +0000 (UTC)
Organization	Stack Usenet News Service
Lines	33
Message-ID	<slrnl39d81.v0j.willem@turtle.stack.nl> (permalink)
References	<f1e06$52314891$5419b3e4$12811@cache90.multikabel.net> <l0rkv6$8gd$1@speranza.aioe.org> <l11m9s$e34$1@dont-email.me>
NNTP-Posting-Host	turtle.stack.nl
Mime-Version	1.0
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
X-Trace	mud.stack.nl 1379185921 5166 2001:610:1108:5010::132 (14 Sep 2013 19:12:01 GMT)
X-Complaints-To	abuse@stack.nl
NNTP-Posting-Date	Sat, 14 Sep 2013 19:12:01 +0000 (UTC)
User-Agent	slrn/0.9.9p1 (OpenBSD)
Xref	csiph.com comp.arch:18045 comp.compression:2023

Cross-posted to 3 groups.

Show key headers only | View raw

Dombo wrote:
) Op 12-Sep-13 7:54, glen herrmannsfeldt schreef:
)> In comp.compression Skybuck Flying <Windows7IsOK@dreampc2006.com> wrote:
)>
)> (snip)
)>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
)>
)>> It's always funny to see how some programmers believe that
)>> Huffman cannot be decoded in parallel.
)>
)> No, not impossible, but not so easy, either.
)
) It is possible and not that hard either, and in fact has been done many 
) times before by many people (myself included). I'm inclined to believe 
) that you'll only see pure serial Huffman decoding in classrooms.

That depends on if you get to control the encoding side.

A small bit of extra work on the encoding side makes it easy to decode
chunks in parallel, otherwise you have several problems, such as the
impossibility to decide the position in the decoded stream without
decoding the previous stream, and the existence of encoded streams
where each position leads to a valid (but different) decoded stream,
only one of which is the correct one.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

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 "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
      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

csiph-web