[Vorbis-dev] RE: nodebytes and leafwords

[Ashok]

hi kuhlen,

what you said is correct. i am talking about how
you are going to arrange these codewords into an
array, i.e. in the function _make_decode_table.
there he uses node bytes and leaf words for memory
management. i got a 24 bit platform. so if i assume
that max. codeword length that could be possible as
24 bits can i allocate a memory of (2 * used entries - 2),
to arrange the whole tree in to an array? but when i am trying
this out it was giving some error. i want to know what
exactly this node bytes and leafwords are effecting the
memory management. i would like to know their significance.

friends pls give me ur valuble suggetins, if anyone knows
that.

regards
ashok.

Message: 3
Date: Tue, 29 Nov 2005 17:57:06 +0100
From: Dominik Kuhlen <dkuhlen at gmx.net>
Subject: Re: [Vorbis-dev] nodebytes,leafwords
To: vorbis-dev at xiph.org
Message-ID: <200511291757.06820.dkuhlen at gmx.net>
Content-Type: text/plain; charset="iso-8859-1"

On Monday 28 November 2005 12:12, Ashok wrote:
> hello all,
>
> we are developing and porting vorbis1decoder on a 24 bit
> platform. in the process we came across somedoubts about
> node bytes and leaf words.
>
> from the specification we got that we are arranging
> the huffman codeword tree into an array. the nodebytes are the
I think it is just the opposite way: you read a list (array) of
codeword-lengths and create a huffman-tree from this list.
> number of bytes that are required to represent a node and
> leafwords are the no. of bytes required to represent the leaf
> i.e the actual codeword.
I'm not sure if I understand you correctly. Here's my interpretation:
You get (extract) a list of codeword lengths.
The indices of this list are the values that are to be coded by the
huffmantree. Heres an example:
let the codeword-length-list be: {1, 2, 3, 5, 4, 7, 5, 7 }
This means:
value 0 is encoded with 1 bit.
value 1 is encoded with 2 bit.
.....
value 5 is encoded with 7 bit.

If you have 'dot' (graphviz) on your system you can generate a picture with
the attached file:
dot -Tpng -o CB06.png < Codebook06.gwdot
>
> is this interpretation correct? if i am wrong please explain
> me what exactly the nodebytes and leafwords represent and their
> significance in the huffman codeword tree arrangement.
I'm not sure what you mean with 'nodebytes' and 'leafwords'
>
> we downloaded 250 test vectors. when we are deocding we got the
> maximum codeword length as 22 bits. practically, what is the maximum
> codeword length that is possible?
This may happen, I just tested a vorbis file and the maximum codeword length
was: 20 bit (minimum length: 1 bit)
>
> looking forward for your suggestions..
>
> regards
> ashok.
> _______________________________________________
> Vorbis-dev mailing list
> Vorbis-dev at xiph.org
> http://lists.xiph.org/mailman/listinfo/vorbis-dev

hope I could help you a little,
Dominik
-------------- next part --------------
/* Warning! This file has been created automagically by huffmantree.cpp */
digraph Codebook {
node [shape = record, height = 0.1];
node0[label = "<f0> 0 | <f1> | <f2> 1"];
node1 [shape = ellipse, label = "0"];
node0:f0 -> node1;
node2[label = "<f0> 0 | <f1> | <f2> 1"];
node3 [shape = ellipse, label = "1"];
node2:f0 -> node3;
node4[label = "<f0> 0 | <f1> | <f2> 1"];
node5 [shape = ellipse, label = "2"];
node4:f0 -> node5;
node6[label = "<f0> 0 | <f1> | <f2> 1"];
node7[label = "<f0> 0 | <f1> | <f2> 1"];
node8[label = "<f0> 0 | <f1> | <f2> 1"];
node9 [shape = ellipse, label = "3"];
node8:f0 -> node9;
node10[label = "<f0> 0 | <f1> | <f2> 1"];
node11 [shape = ellipse, label = "5"];
node10:f0 -> node11;
node12 [shape = ellipse, label = "7"];
node10:f2 -> node12;
node8:f2 -> node10:f1
node7:f0 -> node8:f1
node13 [shape = ellipse, label = "6"];
node7:f2 -> node13;
node6:f0 -> node7:f1
node14 [shape = ellipse, label = "4"];
node6:f2 -> node14;
node4:f2 -> node6:f1
node2:f2 -> node4:f1
node0:f2 -> node2:f1
}

------------------------------

_______________________________________________
Vorbis-dev mailing list
Vorbis-dev at xiph.org
http://lists.xiph.org/mailman/listinfo/vorbis-dev


End of Vorbis-dev Digest, Vol 18, Issue 13
******************************************