Skip to main content

Topic: New FLAC encoder (Read 288376 times) previous topic - next topic

0 Members and 1 Guest are viewing this topic.
  • bhoar
  • [*][*][*][*][*]
  • Members (Donating)
New FLAC encoder
Reply #125
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).
Hacking CD Robots & Autoloaders: http://hyperdiscs.pbwiki.com/

  • lexor
  • [*][*][*]
New FLAC encoder
Reply #126
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.
  • Last Edit: 19 September, 2006, 04:27:20 PM by lexor
The Plan Within Plans

  • pest
  • [*][*][*]
New FLAC encoder
Reply #127
Quote
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

Quote
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
  • [*][*][*][*][*]
  • Developer
New FLAC encoder
Reply #128
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.
  • Last Edit: 19 September, 2006, 04:54:57 PM by jcoalson

  • lexor
  • [*][*][*]
New FLAC encoder
Reply #129
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:

Quote
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.
  • Last Edit: 19 September, 2006, 11:14:36 PM by lexor
The Plan Within Plans

New FLAC encoder
Reply #130
@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: [Select]
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.
  • Last Edit: 19 September, 2006, 09:36:03 PM by Justin Ruggles

New FLAC encoder
Reply #131
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
  • [*]
New FLAC encoder
Reply #132
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
  • [*][*][*]
New FLAC encoder
Reply #133
Justin:
Thank you for the fix.

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

  • Synthetic Soul
  • [*][*][*][*][*]
  • Global Moderator
New FLAC encoder
Reply #134
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.
  • Last Edit: 20 September, 2006, 03:17:39 AM by Synthetic Soul
I'm on a horse.

  • stephanV
  • [*][*][*][*]
New FLAC encoder
Reply #135
'configure && make' is the only thing needed for MingW/MSYS AFAICT.
"We cannot win against obsession. They care, we don't. They win."

  • PrakashP
  • [*]
New FLAC encoder
Reply #136
valgrind confirms that wisodev's patch
Code: [Select]
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: [Select]
==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.
  • Last Edit: 20 September, 2006, 08:06:32 AM by PrakashP

New FLAC encoder
Reply #137
valgrind confirms that wisodev's patch
Code: [Select]
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: [Select]
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
  • Last Edit: 20 September, 2006, 09:12:29 AM by Justin Ruggles

  • Synthetic Soul
  • [*][*][*][*][*]
  • Global Moderator
New FLAC encoder
Reply #138
'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.
I'm on a horse.

  • PrakashP
  • [*]
New FLAC encoder
Reply #139
@Justin

Your patch makes it better, but still not sufficient:
Code: [Select]
==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.
  • Last Edit: 20 September, 2006, 09:35:00 AM by PrakashP

  • Synthetic Soul
  • [*][*][*][*][*]
  • Global Moderator
New FLAC encoder
Reply #140
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: [Select]
$ 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
  • Last Edit: 20 September, 2006, 12:03:28 PM by Synthetic Soul
I'm on a horse.

  • jcoalson
  • [*][*][*][*][*]
  • Developer
New FLAC encoder
Reply #141
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

New FLAC encoder
Reply #142
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
  • Last Edit: 20 September, 2006, 09:37:39 PM by Justin Ruggles

  • HbG
  • [*][*][*][*]
New FLAC encoder
Reply #143
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?
Veni Vidi Vorbis.

  • Synthetic Soul
  • [*][*][*][*][*]
  • Global Moderator
New FLAC encoder
Reply #144
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.
  • Last Edit: 21 September, 2006, 05:06:39 AM by Synthetic Soul
I'm on a horse.

  • wisodev
  • [*][*][*]
  • Developer
New FLAC encoder
Reply #145
FLAKE SVN REVISION 27

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

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

wiso
  • Last Edit: 21 September, 2006, 10:22:33 AM by wisodev

  • Synthetic Soul
  • [*][*][*][*][*]
  • Global Moderator
New FLAC encoder
Reply #146
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?
I'm on a horse.

New FLAC encoder
Reply #147
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
  • [*][*][*][*][*]
  • Global Moderator
New FLAC encoder
Reply #148
 Sounds like I best hold fire.

Good luck with the day off.
I'm on a horse.

  • TBeck
  • [*][*][*][*][*]
  • Developer
New FLAC encoder
Reply #149
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