I have undertaken a small project of writing a Vorbis decoder completely from the spec, with the goal of catching any errors, both typographically and algorithmically, in the spec. My "reference" decoder is also being written in an extremely methodical style, with practically no algorithmic optimization, such that it will be clear that every step has been copied exactly from the spec. During this project, I have promised myself that I will not look at the xiph.org decoder whatsoever, except for copying codec.h for the API so that it conforms to the same API. If my decoder produces bit-identical results to the xiph encoder, it can thus be concluded that the spec is accurate and that the xiph decoder conforms to the spec. I figured I'd publish my notes here as I go along, after I'm done working for one session. I'm going very slowly to help ensure that everything is exactly correct, but I already have a few relatively minor notes: (these will be mostly for Monty, but I'm sure others may have comments) helper.html: * Overview - "int he" -> "in the" * ilog - "returns the *number of* the highest set bit ..." - (reference vorbis-spec-bitpack.html) - "greater than nonzero" -> "greater than zero" - question: ilog defines behavior for signed values. However, it is called sometimes with 32-bit unsigned values (e.g. codebook_decode). Should I (a) cast all these unsigned values to signed, (b) alter ilog to take 32-bit unsigned only, or (c) implement ilog as 64-bit? * float32_unpack - step 3: "shifted left" -> "shifted right" (right?) - step 4: "if ( [mantissa] is nonzero )" -> "if ( [sign] is nonzero )" - question: What are the tolerances on this function? Is it acceptable for me to cast mantissa to double, multiply it by the double returned from pow(2,(dobule)(exponent-788)), and cast the result to float? * lookup1_values - given: return_value ^ codebook_dimensions = codebook_entries -> is this correct: ? (I'm out of school so my algebra is slacking...) -> return_value = log(codebook_entires) / log(codebook_dimensions) -> where return_value truncates the double result to int? <p>vorbis-spec-codebook.html * introduce the variable codebook_codeword_lengths earlier * ordered read, step 4, [n] -> [number] * step 4, put commas around 'inclusive' * ordered read, step 6, increment *by 1* (nitpick) <p>That's all for now. I may have another set later today. -- Kenneth Arnold <ken@arnoldnet.net> - "Know thyself." -------------- next part -------------- A non-text attachment was scrubbed... Name: part Type: application/pgp-signature Size: 190 bytes Desc: not available Url : http://lists.xiph.org/pipermail/vorbis-dev/attachments/20020720/475d6204/part-0001.pgp
Alright, a few more notes for today. Monty, if you could help get my CVS access restored / fixed, I can actually make all the little changes I find instead of putting the burdeon on you for everything, but I'll definately still have questions. However, I'd probably be able to incorporate answers to those sorts of questions into the spec documents also. As per my question in the notes below, I'll probably be able to figure it out myself once I get to the part of the decode that uses it, but I think it really does need to be clearer in the spec. codebook cont'd: * vector value decode: lookup type 1: - steps 1 and 2: zero->0, one->1 * I'm confused about the vector value decodes -- what parameters do they take, what do they return, and what is "this iteration's scalar value"? vorbis-spec-ref.html: * identification header, paragraph under steps: - [audio_rate] -> [audio_sample_rate] - inconsistent naming, upper vs. maximum, lower vs. (minimum?) * time domain transforms - "if any other values" -> "if any value" * floors - variable 'i' is never defined (it's the loop iterator) - replace semicolon with colon after "read the floor type" <p> -- Kenneth Arnold <ken@arnoldnet.net> - "Know thyself." -------------- next part -------------- A non-text attachment was scrubbed... Name: part Type: application/pgp-signature Size: 190 bytes Desc: not available Url : http://lists.xiph.org/pipermail/vorbis-dev/attachments/20020720/7e80ee51/part-0001.pgp
> * Overview > - "int he" -> "in the"corrected> * ilog > - "returns the *number of* the highest set bit ..."corrected, and not that the positionm is one-indexed (counted from 1, not zero)> - (reference vorbis-spec-bitpack.html) > - "greater than nonzero" -> "greater than zero"corrected> - question: ilog defines behavior for signed values. However, it is > called sometimes with 32-bit unsigned values > (e.g. codebook_decode). Should I (a) cast all these unsigned values to > signed, (b) alter ilog to take 32-bit unsigned only, or (c) implement > ilog as 64-bit?No, the spec is not concerned with C style typing. ilog is defined over binary integers, not a specific integer type. When called with an unsigned value, that means it's not possible for the value to be negative and thus the fact that ilog is defined for negative values is irrelevant. <p>> * float32_unpack> - step 3: "shifted left" -> "shifted right" (right?)yes, corrected> - step 4: "if ( [mantissa] is nonzero )" -> "if ( [sign] is nonzero )"yes, corrected> - question: What are the tolerances on this function? Is it acceptable > for me to cast mantissa to double, multiply it by the double returned > from pow(2,(dobule)(exponent-788)), and cast the result to float?yes.> * lookup1_values > - given: > return_value ^ codebook_dimensions = codebook_entries > -> is this correct: ? (I'm out of school so my algebra is slacking...) > -> return_value = log(codebook_entires) / log(codebook_dimensions) > -> where return_value truncates the double result to int?It's vital to never ever rely on floating point rounding convention as you'll get bitten precision problems on specific processors (like early Pentiums). The algorithm here must be integer (brute force if necessary). The algebra is correct, but the float implementation will bite you.> vorbis-spec-codebook.html > * introduce the variable codebook_codeword_lengths earlierdone> * ordered read, step 4, [n] -> [number]corrected> * step 4, put commas around 'inclusive'corrected> * ordered read, step 6, increment *by 1* (nitpick)Oh, *fine* :0) Monty --- >8 ---- List archives: http://www.xiph.org/archives/ Ogg project homepage: http://www.xiph.org/ogg/ To unsubscribe from this list, send a message to 'vorbis-dev-request@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.
On Sat, Jul 20, 2002 at 10:45:54PM -0400, Kenneth Arnold wrote:> Alright, a few more notes for today. Monty, if you could help get my > CVS access restored / fixed, I can actually make all the little > changes I find instead of putting the burdeon on you for everything, > but I'll definately still have questions. However, I'd probably be > able to incorporate answers to those sorts of questions into the spec > documents also.Send me a new ssh key and I'll get that fixed up. You do have a key and write access at the moment, I assume that key is lost?> As per my question in the notes below, I'll probably be able to figure > it out myself once I get to the part of the decode that uses it, but > I think it really does need to be clearer in the spec. > > codebook cont'd: > * vector value decode: lookup type 1: > - steps 1 and 2: zero->0, one->1> * I'm confused about the vector value decodes -- > what parameters do they take, what do they return, > and what is "this iteration's scalar value"?I'm working on making this clearer now.> vorbis-spec-ref.html: > * identification header, paragraph under steps: > - [audio_rate] -> [audio_sample_rate]corrected> - inconsistent naming, upper vs. maximum, lower vs. (minimum?)corrected> * time domain transforms > - "if any other values" -> "if any value"corrected> * floors > - variable 'i' is never defined (it's the loop iterator)corrected> - replace semicolon with colon after "read the floor type"corrected Monty --- >8 ---- List archives: http://www.xiph.org/archives/ Ogg project homepage: http://www.xiph.org/ogg/ To unsubscribe from this list, send a message to 'vorbis-dev-request@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.