New FLAC encoder Options

[bhoar]

Yes. The patched version does work fine here.

However, what is still slightly confusing is that my cygwin compile from the SVN works fine, but wisodev's non-patched compile from the SVN does not.

NB: When I posted above I was confused about wisodev's two compiles, but I realised after posting what he was asking. However, as you can see, I am still confused.

Sometimes bugs only show up due to compiler related attributes, such as the byte-padding required for certain data types, or the order of items in the heap. That is to say, the bug exists in both versions, but depending on which compiler compiled it, the bug might appear immediately (data overwritten was important), occassionally (data overwritten might be discarded often, or LSB of some other musical data, etc.) or not at all (due to enforced data-alignment and/or padding with unused bytes).

[lexor]

what makes even less sense to me is that Levinson algorithm supposed to solve Ax=b for x, given A and b. and that lpc_compute_coefs seems to take 2 vectors and compute the matrix.

it's computing several solutions for several Ax=b, for several x and b, from the same autocorrelation of the original signal. that's the magic. see also http://en.wikipedia.org/wiki/Linear_prediction

that only furthers my confusion, it reiterates that we solving Ax=b for x, given a matrix A and a vector b. but in the function call we only have 1 vector as input, and 1 empty vector and 1 empty matrix:

compute_lpc_coefs(const double *autoc, int max_order, double lpc[][MAX_LPC_ORDER], double *ref)

autoc is the Nx1 vector that is precomputed, max_order is given int, but lpc[][] and *ref are not initialized to anything before they are passed to this function. What is matrix A and vector b then?

I guess my confusion comes from that fact that I don't understand what autoc holds after compute_autocorr is called to fill it. But even then we still apparently trying to solve Ax=b with only 1 of the 3 variables given.

This post has been edited by lexor: Sep 19 2006, 21:27

[pest]

I guess my confusion comes from that fact that I don't understand what autoc holds after compute_autocorr is called to fill it.

http://en.wikipedia.org/wiki/Autocorrelation

But even then we still apparently trying to solve Ax=b with only 1 of the 3 variables given.

the levinson-durbin algo is recursive, so you can model an unknown system as an autoregressive process

[jcoalson]

it is a two step process. the autocorrelation step transforms the problem into the Ra=-r form from the article, this is called the autocorrelation formulation of the original Ax=b.

the autocorrelation matrix R is circulant and can be represented efficiently as a vector. that's the input to the second step that calculates the final filter coefficients for each order with levinson/levinson-durbin recursion.

Josh

p.s. maybe the confusion is on the arguments, autoc is input (vector form of R) and lpc are the output coefficients for each order. because of the recursive nature of the solver you can get the solution for each higher order with only incremental effort, that's why I calculate them all. in shorten the loop aborts when the error estimate stops decreasing to save time.

This post has been edited by jcoalson: Sep 19 2006, 21:54

[lexor]

Thank you for taking time to explain, guys. Right now my greatest confusion comes from notation they use, I can't quite grasp what -r is. From this line in the LPC explanation:

The above equations are called the normal equations or Yule-Walker equations. In matrix form the equations can be equivalently written as: Ra = -r

Yet the "above" line they are talking about seems to say that -r = -R. So are we solving Ra = -R?
Yet below that line, it says that the system Ra = -r is the same as Ra= [1 0 0 0 ... 0]. Is that why we have no vector b in function parameters, because it's assumed to be first unit vector?

in addition to all that, what the hell is R(-j) mean? what kind of a notation is that, negative can't be a valid index.

This post has been edited by lexor: Sep 20 2006, 04:14

[Justin Ruggles]

@wisodev:
another problem found -> "p" switch for padding isn't working at all; it seems that is treated as "s" switch for stereo decorrelation

CODE

D:\documents\music\.work>flake -p 256 -12 37_0-10_12.wav test.flac

Flake: FLAC audio encoder
(c) 2006  Justin Ruggles

invalid stereo decorrelation method: 2. must be 0 or 1.
usage: flake [options] <input.wav> <output.flac>
type 'flake -h' for more details.

I fixed that this morning 9:46 EST. It was missing a break statement after the section which handled the '-p' parsing.
edit: maybe not...I thought I had fixed it. Will look into further.

edit#2: This is now indeed fixed.

This post has been edited by Justin Ruggles: Sep 20 2006, 02:36

[Justin Ruggles]

the improvement is in how the signal is windowed before lpc analysis. we were both working on this at the same time but flake has a shorter release cycle. the method in the upcoming version of FLAC is slower but gives slightly more compression.

On this note, I've been considering doing an adaptive selection between several windows based on either a simple predictability measurement (e.g. energy of fixed 2nd order residual) or maybe a very coarse covariance. Have you done any experimentation with adaptive window selection? I know that the mp4als reference encoder does something like this, but only a binary is supplied for that part of the encoder, not the source.

[yngwin]

Users of Gentoo Linux may be interested in the ebuilds I wrote for flake, both the 0.10 release and the subversion one. See http://berkano.net/bits/2006/09/20/gentoo-overlay

[bukem]

Justin:
Thank you for the fix.

wisodev:
This may get boring after while but I'm waiting for your new native compile

[Synthetic Soul]

While we () are waiting, you could try my cygwin compile.

http://synthetic-soul.co.uk/temp/flake_svn_20060920.7z

@Mangix, if you see this, I got the source using the SVN command line (I'm at home), using the command detailed on Sourceforge. It took less than a minute. I downloaded the SVN zip, unzipped (I just unzipped to my desktop for speed), opened a command line in the "bin" ("\svn-win32-1.4.0\svn-win32-1.4.0\bin") directory and then used the command:

svn co https://svn.sourceforge.net/svnroot/flake-enc flake-enc

This created a folder in my "bin" directory called "flake-enc". I then moved that to somewhere more convenient (a short path with no spaces) and then ran "./configure" then "make" using a cygwin console. A few minutes work in all. I hope this helps. I would be interested to see your MinGW compile (if that's the way you go). I couldn't work out how to do it yesterday.

This post has been edited by Synthetic Soul: Sep 20 2006, 08:17

[stephanV]

'configure && make' is the only thing needed for MingW/MSYS AFAICT.

[PrakashP]

valgrind confirms that wisodev's patch

CODE

diff -urd flake-enc/libflake/encode.c flake-svn-2006-09-19-patched-win32-src/libflake/encode.c
--- flake-enc/libflake/encode.c 2006-09-20 10:39:45.000000000 +0200
+++ flake-svn-2006-09-19-patched-win32-src/libflake/encode.c    2006-09-19 16:59:42.000000000 +0200
@@ -341,11 +341,7 @@
     else                             ctx->lpc_precision = 15;

     /* set maximum encoded frame size in verbatim mode */
-    if(ctx->channels == 2) {
-        s->max_frame_size = 14 + ((ctx->blocksize * 33 + 7) >> 3);
-    } else {
-        s->max_frame_size = 14 + (ctx->blocksize * ctx->channels * 2);
-    }
+    s->max_frame_size = 14 + ((ctx->blocksize * ctx->channels * (ctx->bps+1)) >> 3);
     ctx->max_framesize = s->max_frame_size;

     /* select amount of padding to use in header */

fixes the issue. Otherwise I get:

CODE

==29220== Invalid write of size 4
==29220==    at 0x409EC1: output_residual (bitio.h:103)
==29220==    by 0x40A676: output_subframes (encode.c:729)
==29220==    by 0x40AF62: flake_encode_frame (encode.c:801)
==29220==    by 0x401F21: main (flake.c:378)
==29220==  Address 0x403DAB5 is 4,237 bytes inside a block of size 4,238 alloc'd
==29220==    at 0x4C2006B: malloc (vg_replace_malloc.c:149)
==29220==    by 0x401EAD: main (flake.c:369)
==29220==
==29220== Invalid write of size 1
==29220==    at 0x40AF76: flake_encode_frame (bitio.h:70)
==29220==    by 0x401F21: main (flake.c:378)
==29220==  Address 0x403DAB9 is 3 bytes after a block of size 4,238 alloc'd
==29220==    at 0x4C2006B: malloc (vg_replace_malloc.c:149)
==29220==    by 0x401EAD: main (flake.c:369)
==29220==
==29220== Invalid read of size 1
==29220==    at 0x40B7C0: calc_crc16 (crc.c:71)
==29220==    by 0x40AFC1: flake_encode_frame (encode.c:767)
==29220==    by 0x401F21: main (flake.c:378)
==29220==  Address 0x403DAB6 is 0 bytes after a block of size 4,238 alloc'd
==29220==    at 0x4C2006B: malloc (vg_replace_malloc.c:149)
==29220==    by 0x401EAD: main (flake.c:369)
==29220==
==29220== Invalid read of size 1
==29220==    at 0x40B7C9: calc_crc16 (crc.c:71)
==29220==    by 0x40AFC1: flake_encode_frame (encode.c:767)
==29220==    by 0x401F21: main (flake.c:378)
==29220==  Address 0x403DAB7 is 1 bytes after a block of size 4,238 alloc'd
==29220==    at 0x4C2006B: malloc (vg_replace_malloc.c:149)
==29220==    by 0x401EAD: main (flake.c:369)
==29220==
==29220== Invalid read of size 1
==29220==    at 0x40B7EF: calc_crc16 (crc.c:71)
==29220==    by 0x40AFC1: flake_encode_frame (encode.c:767)
==29220==    by 0x401F21: main (flake.c:378)
==29220==  Address 0x403DAB8 is 2 bytes after a block of size 4,238 alloc'd
==29220==    at 0x4C2006B: malloc (vg_replace_malloc.c:149)
==29220==    by 0x401EAD: main (flake.c:369)
==29220==
==29220== Invalid read of size 1
==29220==    at 0x40B81D: calc_crc16 (crc.c:71)
==29220==    by 0x40AFC1: flake_encode_frame (encode.c:767)
==29220==    by 0x401F21: main (flake.c:378)
==29220==  Address 0x403DAB9 is 3 bytes after a block of size 4,238 alloc'd
==29220==    at 0x4C2006B: malloc (vg_replace_malloc.c:149)
==29220==    by 0x401EAD: main (flake.c:369)

BTW, the svn version has been speeded up by quite some amount in conrast to last release. Some minor speed-up will be commited shortly, I think. So maybe someone likes to bench.

This post has been edited by PrakashP: Sep 20 2006, 13:06

[Justin Ruggles]

valgrind confirms that wisodev's patch

CODE

diff -urd flake-enc/libflake/encode.c flake-svn-2006-09-19-patched-win32-src/libflake/encode.c
--- flake-enc/libflake/encode.c 2006-09-20 10:39:45.000000000 +0200
+++ flake-svn-2006-09-19-patched-win32-src/libflake/encode.c    2006-09-19 16:59:42.000000000 +0200
@@ -341,11 +341,7 @@
     else                             ctx->lpc_precision = 15;

     /* set maximum encoded frame size in verbatim mode */
-    if(ctx->channels == 2) {
-        s->max_frame_size = 14 + ((ctx->blocksize * 33 + 7) >> 3);
-    } else {
-        s->max_frame_size = 14 + (ctx->blocksize * ctx->channels * 2);
-    }
+    s->max_frame_size = 14 + ((ctx->blocksize * ctx->channels * (ctx->bps+1)) >> 3);
     ctx->max_framesize = s->max_frame_size;

     /* select amount of padding to use in header */

While that works, it is not as accurate and does not fix the root of the problem. See if this patch helps.

CODE

Index: libflake/bitio.c
===================================================================
--- libflake/bitio.c    (revision 2)
+++ libflake/bitio.c    (working copy)
@@ -39,7 +39,7 @@
         buf = NULL;
     }
     bw->buffer = buf;
-    bw->buf_end = bw->buffer + len;
+    bw->buf_end = bw->buffer + (((len+3)>>2)<<2); // must be 32-bit aligned
     bw->buf_ptr = bw->buffer;
     bw->bit_left = 32;
     bw->bit_buf = 0;
@@ -77,7 +77,7 @@
         fprintf(stderr, "ERROR: bits=%d val=%u\n", bits, val);
     }*/
    
-    if(bw->eof || bw->buf_ptr >= bw->buf_end) {
+    if(bw->eof || (bw->buf_ptr+3) >= bw->buf_end) {
         bw->eof = 1;
         return;
     }

edit: updated patch

This post has been edited by Justin Ruggles: Sep 20 2006, 14:12

[Synthetic Soul]

'configure && make' is the only thing needed for MingW/MSYS AFAICT.

Yeah, no doubt. The whole thing was new to me yesterday, and I was rushing as I was supposed to be working. I dunno, I tried a few different things and never sucessfully compiled. I was getting very confused between my cygwin and my mingw though! Maybe I'll find some time to get to grips with mingw in the future.

To get this post on topic, I have performed a couple of quick tests using -5 and I would say wisodev's compile takes just over 90% as long to encode as my cygwin compile. I guess I should have tested with the Sourceforge i686 compile as well... Also, two files were compressed to different sizes, although are bit-identical.

BTW, the svn version has been speeded up by quite some amount in conrast to last release. Some minor speed-up will be commited shortly, I think. So maybe someone likes to bench.

Good Lord it's difficult to get a version to test. I knew I shouldn't have gotten into this! If you could let us know when these changes are checked in that would be cool.

I only wanted to test Flake against Yalac, but it's proving a bit of a job to find a starting point.

[PrakashP]

@Justin

Your patch makes it better, but still not sufficient:

CODE

==23819== Invalid write of size 1
==23819==    at 0x40B0EC: flake_encode_frame (bitio.h:71)
==23819==    by 0x401F71: main (flake.c:378)
==23819==  Address 0x403DAB6 is 0 bytes after a block of size 4,238 alloc'd
==23819==    at 0x4C2006B: malloc (vg_replace_malloc.c:149)
==23819==    by 0x401EFD: main (flake.c:369)
==23819==
==23819== Invalid read of size 1
==23819==    at 0x40BE29: calc_crc16 (crc.c:71)
==23819==    by 0x40B137: flake_encode_frame (encode.c:767)
==23819==    by 0x401F71: main (flake.c:378)
==23819==  Address 0x403DAB6 is 0 bytes after a block of size 4,238 alloc'd
==23819==    at 0x4C2006B: malloc (vg_replace_malloc.c:149)
==23819==    by 0x401EFD: main (flake.c:369)

Good Lord it's difficult to get a version to test. I knew I shouldn't have gotten into this! If you could let us know when these changes are checked in that would be cool.

The major speed-ups are already checked in.

This post has been edited by PrakashP: Sep 20 2006, 14:35

[Synthetic Soul]

The major speed-ups are already checked in.

OK, thanks.

What about the errors with Justin's patch? Will they be included?

Edit: K. I had another go with MinGW and it worked just fine. I think my earlier mistake was simply not using the MSYS console to run the apps.

I have checked using objdump and get the following:

CODE

$ objdump -p flake.exe | grep "DLL Name"
        DLL Name: KERNEL32.dll
        DLL Name: msvcrt.dll
        DLL Name: msvcrt.dll

(Note the reliance on msvcrt.dll and not cygwin1.dll.)

Compiles using current SVN (rev 15): cygwin version | mingw version

This post has been edited by Synthetic Soul: Sep 20 2006, 17:03

[jcoalson]

the improvement is in how the signal is windowed before lpc analysis. we were both working on this at the same time but flake has a shorter release cycle. the method in the upcoming version of FLAC is slower but gives slightly more compression.

On this note, I've been considering doing an adaptive selection between several windows based on either a simple predictability measurement (e.g. energy of fixed 2nd order residual) or maybe a very coarse covariance. Have you done any experimentation with adaptive window selection? I know that the mp4als reference encoder does something like this, but only a binary is supplied for that part of the encoder, not the source.

I haven't tried anything like that. I did a brute force exhaustive search test (try all windows for each frame, pick best one) to see what the lower bound was and it didn't end up yielding that much more compression.

when it comes to adding fancy like adaptive schemes I start to worry about patents since currently in libFLAC the encoder and decoder ship together.

Josh

[Justin Ruggles]

The major speed-ups are already checked in.

OK, thanks.

What about the errors with Justin's patch? Will they be included?

Based on Prakash's latest test I didn't quite solve the issue. I'll keep working on it and hopefully be able to apply a definite fix this evening. I just have to find a test sample which makes the valgrind complaint occur. I think it's only very noisy samples which have to be encoded in verbatim mode so as not to actually inflate the file size.

Edit: This issue should be completely fixed in SVN now.

the improvement is in how the signal is windowed before lpc analysis. we were both working on this at the same time but flake has a shorter release cycle. the method in the upcoming version of FLAC is slower but gives slightly more compression.

On this note, I've been considering doing an adaptive selection between several windows based on either a simple predictability measurement (e.g. energy of fixed 2nd order residual) or maybe a very coarse covariance. Have you done any experimentation with adaptive window selection? I know that the mp4als reference encoder does something like this, but only a binary is supplied for that part of the encoder, not the source.

I haven't tried anything like that. I did a brute force exhaustive search test (try all windows for each frame, pick best one) to see what the lower bound was and it didn't end up yielding that much more compression.

when it comes to adding fancy like adaptive schemes I start to worry about patents since currently in libFLAC the encoder and decoder ship together.

Josh

Thanks. That's good to know. It may not be worth the research/testing time if the gain is only trivial.

-Justin

This post has been edited by Justin Ruggles: Sep 21 2006, 02:37

[HbG]

Since i don't have much to add to the technical discussion, all i'll say is this: It'd be very useful to have someone providing proper daily builds, also because this makes promoting flake usage much easier and prompts people to give more feedback. Then i'd happily put my Athlon XP to benchmarking.

As flake is not a reference encoder, patents are less of a worry, right?

[Synthetic Soul]

Edit: This issue should be completely fixed in SVN now.

Thanks Justin.

Compiles using current SVN (rev 27): cygwin version | mingw version

I should point out that I'm just posting these for interest. Due to the speed improvements of wisodev's builds I would wait for him to post if you want to do comparison testing.

This post has been edited by Synthetic Soul: Sep 21 2006, 10:06

[wisodev]

FLAKE SVN REVISION 27

Download binarys:
flake-svn-r27-win32-bin.zip

Download sources:
flake-svn-r27-win32-src.zip

wiso

This post has been edited by wisodev: Sep 21 2006, 15:22

[Synthetic Soul]

Cool, thanks wisodev.

I think this is the version I'll use to compare with Yalac, unless anyone can tell me of any major changes being checked in in the next day or so?

[Justin Ruggles]

Cool, thanks wisodev.

I think this is the version I'll use to compare with Yalac, unless anyone can tell me of any major changes being checked in in the next day or so?

Well, I do have the day off work, so maybe I'll take that as a challenge and work on Flake.
At any rate, if I do implement the next big thing on my list I will probably do another version release several days after. There is 1 change I'll work on this morning that you may want to wait for though. The low-compression levels (0 to 3) will probably get faster.

-Justin

[Synthetic Soul]

Sounds like I best hold fire.

Good luck with the day off.

[TBeck]

Sounds like I best hold fire.

Sorry if i should be asking for too much. You allready have done so much to help me!

Yalac V0.12 will soon be done. After the integration of a seek table and the final tuning of the presets it's performance should not change anymore until the first public release (ok, it may get a bit faster when i disable my debug code).

A test of V0.12 isn't urgent for me, but if it would be easier for you to perform both tests simultaneously, i could work a bit faster.

Thanks

Thomas