On Saturday 28 June 2008 08:10, Rob Landley wrote: > > I see. Someone (you or Manuel) optimized variable bitfield reading > > by reading ahead and changing limit[] format a bit. It's there where bug > > was hiding. Sometimes limit was ending up being 0xffffffff. Which is ok > > if you look at it as an unsigned, but it was signed. > > A) limit is a pointer to an array. I suspect you mean one of the entries in > limit was winding up 0xffffffff?
Yes. > B) That should never happen, I want to know why. > > > Did you receive my mail with a fix? The patch explains that in more > > details. -- > > My response to "that shouldn't happen" was based on your patch, but now I'm > tracing through the program to see what it's actually getting and doing with > the data... > > (This isn't the first way I've found to drive bunzip nuts by the way. A Yep. I am amazed how small decompress_unlzma.c in comparison is. > previous way applied to the original bunzip2, they fixed it in 1.0.3 I think. > > There was also an integer overflow found by the gentoo security guys. But > I'd like to know _why_ the data's off the deep end.) > > Ha! Found the bug. The fix you sent just masks the symptom. > > The failure happens in huffman coding group #4 of your test file. Basically > huffman coding hit a pathological case and is not helping at all here; every > huffman coded symbol takes exactly 8 bits to encode. Might as well not do > huffman coding at all then. It's a crazily balanced fluke huffman tree, > which is why we didn't see it before, but that's not the bug. > > The bug occurs in the following loop: > > // Count symbols coded for at each bit length > for (ii = 0; ii < symCount; ii++) temp[length[ii]]++; > > symCount is 256, and length[ii] for each entry from 0 through 255 is always > 8. > This means that temp[8] gets incremented 256 times. And the problem is that > temp[] is an array of unsigned char, and temp[8] wraps back to 0. > > Later on, limit[maxLen] = pp+temp[maxLen]-1; looks like it should set > limit[8] > to 255, and instead it sets it to -1. Which is where you saw the bug. Yes. > The correct fix is to bump temp[] up to at least a short. Yeah, it'll eat a > bit more stack, but MAX_HUFCODE_BITS is only 20. Bumping it all the way to > an unsigned int would make arm systems noticeably less uncomfortable, they > hate doing math with smaller than int values, the compiler has to output mask > and shift code to do it, bloats the binary and slows stuff down a lot. (It's > an int in my current struct group_data in toybox anyway, no idea what the > busybox version is using.) Just "unsigned" is ok, yes. > Here's a whitespace damaged cut and paste of a patch that fixed it for toybox: > > diff -r 93223118c813 lib/bunzip.c > --- a/lib/bunzip.c Thu Jun 26 22:48:43 2008 -0500 > +++ b/lib/bunzip.c Sat Jun 28 01:03:06 2008 -0500 > @@ -204,7 +204,8 @@ > // literal symbols, plus two run symbols (RUNA, RUNB) > symCount = bd->symTotal+2; > for (jj=0; jj<bd->groupCount; jj++) { > - unsigned char length[MAX_SYMBOLS], temp[MAX_HUFCODE_BITS+1]; > + unsigned char length[MAX_SYMBOLS]; > + unsigned temp[MAX_HUFCODE_BITS+1]; > int minLen, maxLen, pp; > Thanks for excellent analysis! I applied this fix to busybox svn and 1.11.0 patches. BTW, is Firmware Linux capable of producing a bootable system for blackfin? If not, do you want me to try fixing that? -- vda _______________________________________________ busybox mailing list busybox@busybox.net http://busybox.net/cgi-bin/mailman/listinfo/busybox