New FLAC encoder Options

[HbG]

CODE

Encoder Setting    Compression    Encode    Decode
==================================================
Flake -0               71.679%    82.18x    71.13x

I think flac's decoder is quite inefficient... With encoding speed so vastly improved decoding speed may start to hold it back in the great league of lossless formats.

This post has been edited by HbG: Sep 24 2006, 13:18

[MedO]

I really like what I see about Flake develpment, great work! However, I don't know if these SVN builds are safe to use and won't produce "mistakes" with some files. Is there a simple and fast way to verify that the produced files will decode bit-identical and without errors? The official Flac encoder has a verify option to check this IIRC.

[TBeck]

CODE

Encoder Setting    Compression    Encode    Decode
==================================================
Flake -0               71.679%    82.18x    71.13x

I think flac's decoder is quite inefficient... With encoding speed so vastly improved decoding speed may start to hold it back in the great league of lossless formats.

Am i right? You are wondering, why decoding isn't faster than encoding?

I have to go a bit technical, to explain it.

To simplify it:

The encoder has to perform tree operations:

A) Analyze the signal and select an optimal prediction method.
B) Prediction: Predict the next sample and calculate the difference (residual) between the prediction and the true sample.
C) BitIO: Write the residual into the bitstream (file).

The decoder has to perform two operations:

A) BitIO: Read the residual from the bitstream (file).
B) Prediction: Predict the next sample and add the residual from (A) to get the true sample value.

Differences between encoding and decoding:

For Flake -0, signal analysis (A) of the encoder is very simple and fast.

The calculations encoder and decoder have to perform for the prediction of the fast -0 mode are absolutely simple, can be performed ultra fast and should be equally fast on the encoder and decoder side.

But the difference of the processing requirements for the prediction in encoder and decoder is quite small compared to the difference for the BitIO!

One important operation, processors have to perform, is a conditional jump. It is needed, if -depending on a certain condition- two different actions have to be performed.

But modern processors like to know as soon as possible what will be going on later. In the case of a conditional jump, they had to wait until the critical condition has been calculated. Because they don't want to wait, they try to predict the result of the condition based upon their knowledge about prior excecutions of the
conditional jump.

This works quite well, if the condition follows a simple (repetitive) pattern, for instance: The condition is 5 times true, than 1 time false, than 5 times true. Then the conditional jump will be called predictable.

The worst case is a conditional jump, which is following an unpredictable pattern. Modern processors may have to wait 20 and more clock cycle, if they have performed a misprediction!

Compare this to the about 0.5 clock cycles needed for simple operations like additions or substractions!

What is important: The BitIO of the encoder needs far less conditional jumps (if well implemented) than the decoder, and the jumps on the decoder side will be unpredictable most of the time.

A simplified example:

On average 1 mispredictions per sample on the encoder side = 20 clock cycles
On average 3 mispredictions per sample on the dncoder side = 60 clock cycles

And possibly 5 simple cpu operations for the prediction: 5 * 0.5 = 2.5 clock cycles.

Sorry, my english is too limited for a good explaination. I hope, you can understand.

This post has been edited by TBeck: Sep 24 2006, 14:21

[HbG]

MedO: Use FlacTester. Just give it a directory and it will recursively work it's way through it and all subdirs testing all flacs it finds. Ideal for keeping your flac collection in proper working order.

TBeck: thanks for the explanation, i understand. Indeed it seemingly goes against nature to have faster encoding than decoding..
It would also mean the difference should be even greater for P4 processors.

This post has been edited by HbG: Sep 24 2006, 14:18

[MedO]

MedO: Use FlacTester. Just give it a directory and it will recursively work it's way through it and all subdirs testing all flacs it finds. Ideal for keeping your flac collection in proper working order.

Thanks for the tip. So I can rely on Flake producing correct checksums? Just want to be sure :-)

This post has been edited by MedO: Sep 24 2006, 14:54

[HbG]

It's a md5 hash, if flake manages to produce a corrupt hash that fits the corrupt output, i'd be very impressed.

This post has been edited by HbG: Sep 24 2006, 15:25

[Justin Ruggles]

Justin. I pulled revision 2 from SVN, and tried to build this on Mac OS 10.47 PowerPC/ GCC 4.0.1 (Xcode Tools 2.4). But it errors out like this:$ ./configure
source path /Users/krmathis/Downloads/flake-enc
C compiler cc
make make
CPU powerpc (generic)
big-endian yes
inttypes.h yes
AltiVec enabled yes
debug symbols yes
strip symbols yes
optimize yes
Creating config.mak and config.h...
$ make
make -C libflake all

** Snip **

cc -O3 -no-cpp-precomp -pipe -force_cpusubtype_ALL -Wno-sign-compare -fomit-frame-pointer -faltivec -g -Wdeclaration-after-statement -Wall -Wno-switch -mdynamic-no-pic -DHAVE_CONFIG_H -I. -I.. -I/Users/krmathis/Downloads/flake-enc/libflake -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -D_ISOC9X_SOURCE -c -o wav.o wav.c
cc -L../libflake -Wl,-dynamic,-search_paths_first -g -o flake_g flake.o wav.o -lflake
/usr/bin/ld: Undefined symbols:
_bswap_16
collect2: ld returned 1 exit status
make[1]: *** [flake_g] Error 1
make: *** [progs] Error 2

Sorry...I did not see this originally. It looks like it might have to do with byteswap.h. I'll look into it.

This post has been edited by Justin Ruggles: Sep 24 2006, 16:07

[krmathis]

Sorry...I did not see this originally. It looks like it might have to do with byteswap.h. I'll look into it.

Thank you!

[jcoalson]

It's a md5 hash, if flake manages to produce a corrupt hash that fits the corrupt output, i'd be very impressed.

md5 is only useful as an error-detection mechanism after a verified-good encoding. there are many ways the encoder can mess up the data going in and still create a file with a correct md5. that's why there's a --verify mode in flac, and why the flac test suite uses --verify as well as encodes/decodes/compares many thousands of different streams/encoding combinations before a release.

Josh

[Justin Ruggles]

It's a md5 hash, if flake manages to produce a corrupt hash that fits the corrupt output, i'd be very impressed.

md5 is only useful as an error-detection mechanism after a verified-good encoding. there are many ways the encoder can mess up the data going in and still create a file with a correct md5. that's why there's a --verify mode in flac, and why the flac test suite uses --verify as well as encodes/decodes/compares many thousands of different streams/encoding combinations before a release.

Josh

I definitely agree. It's not nearly as hard as it may seem to produce a false MD5 which matches decoded output. This can happen if the wav data gets corrupted (by either program bugs or by machine-related errors) anywhere between the wav file read and the MD5 update.

If I ever have the time and there is a demand for it, I might import FFmpeg's FLAC decoder into Flake for verification during encoding. For now I'll add it to the TODO list.

-Justin

[sundance]

HbG,

I think flac's decoder is quite inefficient... With encoding speed so vastly improved decoding speed may start to hold it back in the great league of lossless formats.

You could be right.
Some time ago I did some tests with flacdec, and despite running it under cygwin, it was faster than flac -d. Since I don't have the necessary tools to build an optimized win32-compilation, I didn't test further...

[edit]
Here's my test results (12 flac files, encoded with flac -8, totalling 447.635.340 bytes) for decoding to nul:
a) flac -d -o nul [file]: 34,31 sec (avg.)
b) flacdec -o nul [file]: 12,21 sec (avg.)
Although flacdec doesn't "check MD5 signature of audio data", I don't think that's the culprit...

.sundance.

This post has been edited by sundance: Sep 25 2006, 11:41

[MedO]

I definitely agree. It's not nearly as hard as it may seem to produce a false MD5 which matches decoded output. This can happen if the wav data gets corrupted (by either program bugs or by machine-related errors) anywhere between the wav file read and the MD5 update.

If I ever have the time and there is a demand for it, I might import FFmpeg's FLAC decoder into Flake for verification during encoding. For now I'll add it to the TODO list.

-Justin

So the only way I can be sure is checking the decoded audio against the original? I guess I could write a script to do this, but that would probably end any speed gain I got with Flake.

This post has been edited by MedO: Sep 25 2006, 08:44

[HbG]

Whoops, i stand corrected on the MD5's. I didn't think of the wav data getting corrupted before being hashed, although technically that does not indicate a fault in the encoding routines.

Sundance, you're right, i had even used flacdec before and forgot about it. As it's not a reference decoder i'm not using it in combination with flake. Still a better compile would be nice to see just what it can do, it does decode variable blocksize properly and without measurable speed penalty for the sample i used.

I did a little benchmark with a flake -8 encoded file, flac -d gives me 151.88x, foobar 180.23x, flacdec 265.60x
Sundance's flacdec-to-flac ratio is 2.81, mine is 1.75, there is something strange going on here.

Flacdec generates an output stream with a bandwidth of over 45MB/s. I couldn't find a suitable md5 benchmark for windows quickly but i did find this. Looks like the impact of hashing on overal performance is significant, but nowhere near enough to explain the whole difference.

MedO, that's the tradeoff of new software, it needs testing.

This post has been edited by HbG: Sep 25 2006, 13:21

[sundance]

Sundance's flacdec-to-flac ratio is 2.81, mine is 1.75, there is something strange going on here.

I tested on a P4@2.8 GHz using that "script" along with 4NT (enhanced command shell).
All files resided on a fast local hard drive; the output went to nul: device.

CODE

timer
for %f in (*.flac) flac -f -d -o nul "%f"
timer
timer
for %f in (*.flac) flacdec -o nul "%f"
timer

Result:

CODE

Timer 1 on: 15:12:02
Timer 1 off: 15:12:37  Elapsed: 0:00:35,53
Timer 1 on: 15:12:37
Timer 1 off: 15:12:50  Elapsed: 0:00:12,91

I ran this test 5 times to eleminate disc caching related timing differences and didn't use the best and worst result to calculate the average time needed. Would be interested if you acually created wav files or if also redirected to nul...

.sundance.

P.S. Hope this discussion isn't to much OT...

[MedO]

MedO, that's the tradeoff of new software, it needs testing.

I wrote a small wrapper script using flake, md5sum and flac (for decoding). I can post it here if anyone's interested, but only after I improved it a bit, since this was only for quick testing. Btw, this is still a good deal faster than using the official encoder when both run at -8.

[jcoalson]

I tested on a P4@2.8 GHz using that "script" along with 4NT (enhanced command shell).
All files resided on a fast local hard drive; the output went to nul: device.

CODE

timer
for %f in (*.flac) flac -f -d -o nul "%f"
timer
timer
for %f in (*.flac) flacdec -o nul "%f"
timer

I don't know what "-o nul" means to flacdec but to flac that means output to a file called "nul" so you are counting the i/o time, which is probably half the total time. if you want to eliminate that, use -t instead of -d.

also, flac decoding is fast enough that md5 checking does take a significant amount of time. but it would still add only 10-20% I think, not double. you can't turn off md5 checking in the command line decoder (unless you use metaflac to set the md5 sum of the file to all zeroes)

the flac binary for windows that I release is compiled with msvc6 which might generate slower code. but it has a lot of assembly optimization, so I think this 1.7-2.8x difference is because of something else (like file i/o) not comparing apples to apples.

Josh

[Justin Ruggles]

Here's my test results (12 flac files, encoded with flac -8, totalling 447.635.340 bytes) for decoding to nul:
a) flac -d -o nul [file]: 34,31 sec (avg.)
b) flacdec -o nul [file]: 12,21 sec (avg.)
Although flacdec doesn't "check MD5 signature of audio data", I don't think that's the culprit...

In my tests, the MD5 checking accounts for about 25% of the decoding time in flac (using flac -t).

[kjoonlee]

I think NUL is the DOS/Windows equivalent of /dev/null.

[sundance]

Josh,

sorry for not comparing objectively.
I assumed that flac also used the nul: device in my commandline since no file was actually generated. But that was of course a wrong assumption since you can't create such a file in dos/win/win32. I'll try to repeat my little "test" with flac -t as you've suggested when I'm back home at my computer.

And please don't get me wrong: Nagging about flac is the least I want to do - I've been a long time flac user and lover and because of that I'm really excited with all the progress of the flac format.

.sundance.

[krmathis]

Sorry...I did not see this originally. It looks like it might have to do with byteswap.h. I'll look into it.

Thank you!

Justin. Can you please let me know when you think you have fixed this?

[jcoalson]

Josh,

sorry for not comparing objectively.

no problem!

I assumed that flac also used the nul: device in my commandline since no file was actually generated. But that was of course a wrong assumption since you can't create such a file in dos/win/win32. I'll try to repeat my little "test" with flac -t as you've suggested when I'm back home at my computer.

hmm... if it didn't write a file, maybe windows C lib is interpreting nul on its own. with nul it might still count time copying the output data around, not sure. the comparison also depends on how exactly flacdec handles '-o nul'

And please don't get me wrong: Nagging about flac is the least I want to do - I've been a long time flac user and lover and because of that I'm really excited with all the progress of the flac format.

no, that's fine, it's just that I really don't know how another decoder could be 2x faster than the reference, that would be a huge improvement since the reference decoder is already optimized. a faster encoder is easy to believe.

Josh

[Justin Ruggles]

Sorry...I did not see this originally. It looks like it might have to do with byteswap.h. I'll look into it.

Thank you!

Justin. Can you please let me know when you think you have fixed this?

Well, I don't have a mac to test on, so I'm kinda at a loss. I did change some of the configuration options, but I doubt they will help. I'm wondering if maybe bswap_32 is being redefined somewhere... Try the patch below. If it doesn't fix the problem, at least it might point me in the right direction.
-Justin

CODE

Index: flake/wav.c
===================================================================
--- flake/wav.c    (revision 46)
+++ flake/wav.c    (working copy)
@@ -537,7 +537,7 @@
#ifdef WORDS_BIG_ENDIAN
         uint16_t *buf16 = (uint16_t *)buffer;
         for(i=0; i<nsmp; i++) {
-            buf16[i] = bswap_16(buf16[i]);
+            buf16[i] = flake_bswap_16(buf16[i]);
         }
#endif
         if(wf->source_format != WAV_SAMPLE_FMT_S16) return -1;
@@ -568,7 +568,7 @@
#ifdef WORDS_BIG_ENDIAN
             uint32_t *buf32 = (uint32_t *)buffer;
             for(i=0; i<nsmp; i++) {
-                buf32[i] = bswap_32(buf32[i]);
+                buf32[i] = flake_bswap_32(buf32[i]);
             }
#endif
             if(wf->source_format != WAV_SAMPLE_FMT_FLT) return -1;
@@ -591,7 +591,7 @@
#ifdef WORDS_BIG_ENDIAN
         uint64_t *buf64 = (uint64_t *)buffer;
         for(i=0; i<nsmp; i++) {
-            buf64[i] = bswap_64(buf64[i]);
+            buf64[i] = flake_bswap_64(buf64[i]);
         }
#endif
         if(wf->source_format != WAV_SAMPLE_FMT_DBL) return -1;
Index: bswap.h
===================================================================
--- bswap.h    (revision 54)
+++ bswap.h    (working copy)
@@ -8,24 +8,24 @@

#include "config.h"

-static inline uint16_t bswap_16(uint16_t x){
+static inline uint16_t flake_bswap_16(uint16_t x){
     return (x>>8) | (x<<8);
}

-static inline uint32_t bswap_32(uint32_t x){
+static inline uint32_t flake_bswap_32(uint32_t x){
     x= ((x<<8)&0xFF00FF00) | ((x>>8)&0x00FF00FF);
     return (x>>16) | (x<<16);
}

-static inline uint64_t bswap_64(uint64_t x)
+static inline uint64_t flake_bswap_64(uint64_t x)
{
     union {
         uint64_t ll;
         uint32_t l[2];
     } w, r;
     w.ll = x;
-    r.l[0] = bswap_32(w.l[1]);
-    r.l[1] = bswap_32(w.l[0]);
+    r.l[0] = flake_bswap_32(w.l[1]);
+    r.l[1] = flake_bswap_32(w.l[0]);
     return r.ll;
}

@@ -36,13 +36,13 @@
#define be2me_16(x) (x)
#define be2me_32(x) (x)
#define be2me_64(x) (x)
-#define le2me_16(x) bswap_16(x)
-#define le2me_32(x) bswap_32(x)
-#define le2me_64(x) bswap_64(x)
+#define le2me_16(x) flake_bswap_16(x)
+#define le2me_32(x) flake_bswap_32(x)
+#define le2me_64(x) flake_bswap_64(x)
#else
-#define be2me_16(x) bswap_16(x)
-#define be2me_32(x) bswap_32(x)
-#define be2me_64(x) bswap_64(x)
+#define be2me_16(x) flake_bswap_16(x)
+#define be2me_32(x) flake_bswap_32(x)
+#define be2me_64(x) flake_bswap_64(x)
#define le2me_16(x) (x)
#define le2me_32(x) (x)
#define le2me_64(x) (x)

[krmathis]

Well, I don't have a mac to test on, so I'm kinda at a loss. I did change some of the configuration options, but I doubt they will help. I'm wondering if maybe bswap_32 is being redefined somewhere... Try the patch below. If it doesn't fix the problem, at least it might point me in the right direction.
-Justin

I understand that you have no way to test this, since you don't have access to a Mac. But I am more than willing to perform the tests needed. If that helps?

Ok, I had to manually edit the files according to the patch you listed. Because I could not get patch to recognize the patch file I created with nano.

Revision 61 with the patched files failed just like before:

cc -L/Users/krmathis/.Trash/flake-enc/libflake -Wl,-dynamic,-search paths_first -g -o flake_g flake.o wav.o -lflake
/usr/bin/ld: Undefined symbols:
_bswap_16
collect2: ld returned 1 exit status
make[1]: *** [flake_g] Error 1
make: *** [progs] Error 2

The problem seems to be line #277 in flake-enc/libflake/md5.c
Cause if I change "bswap_16" to "flake_bswap_16" the error message change according to it.


Edit: I removed the above mentioned line, and it compiled successfully!

CODE

-        sig16[i] = bswap_16(sig16[i]);

It launches, but I don't know how to test if it works as expected...


Edit 2:
It compressed a wav file successfully. But the result can't be right!

40801624 Sep 25 20:33 01 - Speak to Me - Breathe In the Air.flac
22205524 Sep 23 14:27 01 - Speak to Me - Breathe In the Air.m4a
41952016 Sep 25 20:32 01 - Speak to Me - Breathe In the Air.wav

The resulting FLAC file was only compressed to 97% of the original one. While the ALAC (.m4a) file compressed to ~60%.

Flake: FLAC audio encoder
© 2006 Justin Ruggles

Signed 16-bit 44100 Hz stereo
samples: 10486980

block size: 4608
variable: none
prediction type: levinson-durbin
prediction order: 1,8
partition order: 0,6
order method: estimate
stereo method: mid-side
header padding: 4096

progress: 100% | ratio: 0.973 | bitrate: 1372.5 kbps | bytes: 40801624

Was this caused by the line I edited out?

This post has been edited by krmathis: Sep 25 2006, 19:38

[Justin Ruggles]

The problem seems to be line #277 in flake-enc/libflake/md5.c
Cause if I change "bswap_16" to "flake_bswap_16" the error message change according to it.

Fixed. I forgot to #include "bswap.h" at the top of md5.c.

-Justin

[Justin Ruggles]

It compressed a wav file successfully. But the result can't be right!

40801624 Sep 25 20:33 01 - Speak to Me - Breathe In the Air.flac
22205524 Sep 23 14:27 01 - Speak to Me - Breathe In the Air.m4a
41952016 Sep 25 20:32 01 - Speak to Me - Breathe In the Air.wav

The resulting FLAC file was only compressed to 97% of the original one. While the ALAC (.m4a) file compressed to ~60%.
...
Was this caused by the line I edited out?

I hope so...but I sort of doubt it. Play back the flac file. I suspect it's all noise. If you try rev67 and still have the problem please speak up and I'll investigate.