Home > Archive > Compression > May 2004 > data transform
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| Davor@Home 2004-05-12, 9:29 pm |
| is it possible to transform data stream in such way
that output stream does not contain sequence of
two same bytes in a row?
| |
| Errol Smith 2004-05-12, 9:29 pm |
| On Sun, 9 May 2004 07:25:55 +0200, "Davor@Home"
<davor.tarandek@ck.tel.hr> wrote:
>is it possible to transform data stream in such way
>that output stream does not contain sequence of
>two same bytes in a row?
Sure, just follow every byte with another byte that is the XOR of
itself. Or that is the previous byte minus one or something.
(I'm guessing you really wanted something that doesnt enlarge the
stream too much - but you didn't specify that :-)
Errol Smith
errol <at> ros (dot) com [period] au
| |
| Davor@Home 2004-05-12, 9:29 pm |
| > Sure, just follow every byte with another byte that is the XOR of
> itself. Or that is the previous byte minus one or something.
but the next byte could have same value as xored duplicate ...
> (I'm guessing you really wanted something that doesnt enlarge the
> stream too much - but you didn't specify that :-)
exactly ... up to 5% enlargement would be tolerable ...
but for startes i'll use anything
| |
| Willem 2004-05-12, 9:29 pm |
| Davor@Home wrote:
)> Sure, just follow every byte with another byte that is the XOR of
)> itself. Or that is the previous byte minus one or something.
)
) but the next byte could have same value as xored duplicate ...
)
)> (I'm guessing you really wanted something that doesnt enlarge the
)> stream too much - but you didn't specify that :-)
)
) exactly ... up to 5% enlargement would be tolerable ...
) but for startes i'll use anything
Well, you can simply interpret the original stream as if it's an arithmetic
encoding of a 255-symbol stream and decode the symbols. You can then
interpret that as if it's a 256-symbol stream where the '0' doesn't occur.
As the final step, simply treat that as if it's delta encoding, and you
have a stream where no byte is the same as the previous.
If my math is correct, this enlarges the stream by somewhat under 0.1%.
I think you can make some shortcuts to this to get a simpler program,
eliminate the ending problems of an arith coder, etc.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| George King 2004-05-12, 9:29 pm |
| Principly, to disallow two consecutive bytes to be the same reduces
the amount of information that can be represented given the same
number of bytes.
Such a transformation would necessarily result in data that is larger
in size.
An effective way is to develop an encoding that identifies two
consecutive being the same as 'special'.
George
Gr[url=http://ladychatterleyslover.grabafreebie.com/WomanInLove.html]a[/url][url=http://womaninlove.grabafreebie.com/Frankenstein.html]b[/url][url=http://frankenstein.grabafreebie.com/Dracula.html]A[/url][url=http://dracula.grabafreebie.com/LairOfTheWhite
Worm.html]F[/url][url=http://lairofthewhiteworm.grabafreebie.com/PrideAndPrejudice.html]r[/url][url=http://prideandprejudice.grabafreebie.com/RobRoy.html]e[/url][url=http://robroy.grabafreebie.com/MrsDalloway.html]e[/url][url=http://mrsdalloway.grabafreeb
ie.com/Kidnapped.html]b[/url][url=http://kidnapped.grabafreebie.com/TheStrangeCaseOfDrJekyllAndMrHyde.html]i[/url][url=http://thestrangecaseofdrjekyllandmrhyde.grabafreebie.com/TreasureIsland.html]e[/url]
Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com
| |
| Davor@Home 2004-05-12, 9:29 pm |
|
"Willem" <willem@stack.nl> wrote in message
news:slrnc9si39.1vl5.willem@toad.stack.nl...
> Davor@Home wrote:
> )> Sure, just follow every byte with another byte that is the XOR of
> )> itself. Or that is the previous byte minus one or something.
> )
> ) but the next byte could have same value as xored duplicate ...
> )
> )> (I'm guessing you really wanted something that doesnt enlarge the
> )> stream too much - but you didn't specify that :-)
> )
> ) exactly ... up to 5% enlargement would be tolerable ...
> ) but for startes i'll use anything
>
> Well, you can simply interpret the original stream as if it's an
arithmetic
> encoding of a 255-symbol stream and decode the symbols. You can then
> interpret that as if it's a 256-symbol stream where the '0' doesn't occur.
> As the final step, simply treat that as if it's delta encoding, and you
> have a stream where no byte is the same as the previous.
running a arithmetic decoder on input stream increases size by 69.4084%!!!
obviously i'm doing something wrong!!
> If my math is correct, this enlarges the stream by somewhat under 0.1%.
> I think you can make some shortcuts to this to get a simpler program,
> eliminate the ending problems of an arith coder, etc.
ending is not an issue ...
| |
| Willem 2004-05-12, 9:29 pm |
| )> Well, you can simply interpret the original stream as if it's an
) arithmetic
)> encoding of a 255-symbol stream and decode the symbols. You can then
)> interpret that as if it's a 256-symbol stream where the '0' doesn't occur.
)> As the final step, simply treat that as if it's delta encoding, and you
)> have a stream where no byte is the same as the previous.
Davor wrote:
) running a arithmetic decoder on input stream increases size by 69.4084%!!!
) obviously i'm doing something wrong!!
The arith decoder needs to have a fixed model of 255 symbols, where each
symbol has the same probability. You don't want to have an ataptive
decoder or something like that.
)> If my math is correct, this enlarges the stream by somewhat under 0.1%.
)
)> I think you can make some shortcuts to this to get a simpler program,
)> eliminate the ending problems of an arith coder, etc.
)
) ending is not an issue ...
It is if the last byte gets mangled. ^_^
Oh, by the way, you can probably also adapt a rangecoder to use 255
symbols instead of 256, that should work equally well (modulo rounding).
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| Falk Hueffner 2004-05-12, 9:29 pm |
| "Davor@Home" <davor.tarandek@ck.tel.hr> writes:
> is it possible to transform data stream in such way that output
> stream does not contain sequence of two same bytes in a row?
Output the first 7 bits of a byte. If they are equal to the first 7
bits of the previous output byte, output the opposite of the 8th bit
in the previous output byte, otherwise just output the 8th bit. The
decoder can easily recognize which case was used. That way you fit 8
bits into 8 in 127 of 128 cases and 7 into 8 in 1 of 128 cases,
resulting in about 1% expansion. If the data is too regular and you
need to stuff a byte too often, xor it with a random number generator.
--
Falk
| |
| Davor@Home 2004-05-12, 9:29 pm |
|
"Willem" <willem@stack.nl> wrote in message
news:slrnc9uj16.174h.willem@toad.stack.nl...
> )> Well, you can simply interpret the original stream as if it's an
> ) arithmetic
> )> encoding of a 255-symbol stream and decode the symbols. You can then
> )> interpret that as if it's a 256-symbol stream where the '0' doesn't
occur.
> )> As the final step, simply treat that as if it's delta encoding, and you
> )> have a stream where no byte is the same as the previous.
>
> Davor wrote:
>
> ) running a arithmetic decoder on input stream increases size by
69.4084%!!!
> ) obviously i'm doing something wrong!!
>
> The arith decoder needs to have a fixed model of 255 symbols, where each
> symbol has the same probability. You don't want to have an ataptive
> decoder or something like that.
>
i do have adaptive decoder ... i'll try without updating the model ..
> )> If my math is correct, this enlarges the stream by somewhat under 0.1%.
> )
> )> I think you can make some shortcuts to this to get a simpler program,
> )> eliminate the ending problems of an arith coder, etc.
> )
> ) ending is not an issue ...
>
> It is if the last byte gets mangled. ^_^
>
>
> Oh, by the way, you can probably also adapt a rangecoder to use 255
> symbols instead of 256, that should work equally well (modulo rounding).
>
i'll try that too ...
| |
| Davor@Home 2004-05-12, 9:29 pm |
|
"Falk Hueffner" <hueffner@informatik.uni-tuebingen.de> wrote in message
news:87k6zkwr3y.fsf@informatik.uni-tuebingen.de...
> "Davor@Home" <davor.tarandek@ck.tel.hr> writes:
>
>
> Output the first 7 bits of a byte. If they are equal to the first 7
> bits of the previous output byte, output the opposite of the 8th bit
> in the previous output byte, otherwise just output the 8th bit. The
> decoder can easily recognize which case was used. That way you fit 8
> bits into 8 in 127 of 128 cases and 7 into 8 in 1 of 128 cases,
> resulting in about 1% expansion. If the data is too regular and you
> need to stuff a byte too often, xor it with a random number generator.
>
it works, but not on nibble level ... expansion is somewhat bigger (2.5% -
4% on my stream)
but still under 5%
thank you
| |
| Davor@Home 2004-05-12, 9:29 pm |
|
"Davor@Home" <davor.tarandek@ck.tel.hr> wrote in message
news:c7nk2u$r17$2@ls219.htnet.hr...
>
> "Falk Hueffner" <hueffner@informatik.uni-tuebingen.de> wrote in message
> news:87k6zkwr3y.fsf@informatik.uni-tuebingen.de...
>
> it works, but not on nibble level ... expansion is somewhat bigger (2.5% -
> 4% on my stream)
> but still under 5%
>
correction ... it doesn't work ... expansion is over 10% on nibble level
i made an stupid error in math ...
and that algorithm doesn't work at all on byte level ...
the following sequence produces two same bytes in a row :
0, 1, 0
or in bits :
00000001
00000000
00000001
algorithm produces following output :
first byte is copied :
00000001
second byte is stuffed :
000000000
third byte is also stuffed:
000000011
split this to 8 bits and you get following output :
00000001
00000000 | two zeroes
00000000 | in a row !!!
11000000
| |
| Willem 2004-05-12, 9:29 pm |
| Davor@Home wrote:
) correction ... it doesn't work ... expansion is over 10% on nibble level
) i made an stupid error in math ...
)
) and that algorithm doesn't work at all on byte level ...
) the following sequence produces two same bytes in a row :
) 0, 1, 0
)
) or in bits :
)
) 00000001
) 00000000
) 00000001
)
) algorithm produces following output :
)
) first byte is copied :
) 00000001
) second byte is stuffed :
) 000000000
) third byte is also stuffed:
) 000000011
)
) split this to 8 bits and you get following output :
)
) 00000001
) 00000000 | two zeroes
) 00000000 | in a row !!!
) 11000000
I think you misunderstood the algorithm slightly.
The idea is to unstuff from 7 bits, instead of stuffing to 9 bits.
So it's 0, 1, 0:
in bits:
00000000
00000001
00000000
algorithm produces following output:
first byte is copied:
00000000
second 7 bits are copied, and stuffed with a 1 because it matches:
00000001
another 7 bits are copied, and the 8th is copied too:
10000000
The last bit is copied:
0
This algorithm is a lot easier to understand than the arithcoding one, but
it's not 'stable' (as in, it doesn't always produce the same number of
bits.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| Salvador Fandiņo 2004-05-12, 9:29 pm |
| Davor@Home wrote:
> is it possible to transform data stream in such way
> that output stream does not contain sequence of
> two same bytes in a row?
another way:
you can see your stream as a big number in base 256,
convert your number to base 255 and write it encoding every digit
on a byte but considering a gap on the 0-255 byte range for the
previous value.
- Salvador
| |
| Willem 2004-05-12, 9:29 pm |
| Salvador wrote:
) another way:
)
) you can see your stream as a big number in base 256,
)
) convert your number to base 255 and write it encoding every digit
) on a byte but considering a gap on the 0-255 byte range for the
) previous value.
Technically speaking that's the same as rangecoding using 255 symbols and
arithdecoding as 255 symbols. ^_^
Although when you view it as converting base, it's a quite different
approach, probably easier to get right.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| Davor@Home 2004-05-12, 9:29 pm |
|
"Willem" <willem@stack.nl> wrote in message
news:slrnc9unp4.1vu5.willem@toad.stack.nl...
> Davor@Home wrote:
> ) correction ... it doesn't work ... expansion is over 10% on nibble level
> ) i made an stupid error in math ...
> )
> ) and that algorithm doesn't work at all on byte level ...
> ) the following sequence produces two same bytes in a row :
> ) 0, 1, 0
> )
> ) or in bits :
> )
> ) 00000001
> ) 00000000
> ) 00000001
> )
> ) algorithm produces following output :
> )
> ) first byte is copied :
> ) 00000001
> ) second byte is stuffed :
> ) 000000000
> ) third byte is also stuffed:
> ) 000000011
> )
> ) split this to 8 bits and you get following output :
> )
> ) 00000001
> ) 00000000 | two zeroes
> ) 00000000 | in a row !!!
> ) 11000000
>
> I think you misunderstood the algorithm slightly.
> The idea is to unstuff from 7 bits, instead of stuffing to 9 bits.
obviously ...
> So it's 0, 1, 0:
>
> in bits:
>
> 00000000
> 00000001
> 00000000
>
> algorithm produces following output:
>
> first byte is copied:
> 00000000
> second 7 bits are copied, and stuffed with a 1 because it matches:
> 00000001
> another 7 bits are copied, and the 8th is copied too:
> 10000000
> The last bit is copied:
> 0
>
ah .. yes ...
>
> This algorithm is a lot easier to understand than the arithcoding one, but
> it's not 'stable' (as in, it doesn't always produce the same number of
> bits.
>
no problem ...
| |
| Phil Carmody 2004-05-12, 9:29 pm |
| Salvador Fandiņo <salvafg@terra.es> writes:
> Davor@Home wrote:
>
> another way:
>
> you can see your stream as a big number in base 256,
Streams may be infinite, (integer) numbers may not.
For example - what would the stream consisting of nothing
but hex AA map to? What's the lowest base-255 digit? Or
the highest base-255 digit?
Phil
--
1st bug in MS win2k source code found after 20 minutes: scanline.cpp
2nd and 3rd bug found after 10 more minutes: gethost.c
Both non-exploitable. (The 2nd/3rd ones might be, depending on the CRTL)
| |
| Willem 2004-05-12, 9:29 pm |
| Phil wrote:
) Salvador Fandiņo <salvafg@terra.es> writes:
)
)> Davor@Home wrote:
)> > is it possible to transform data stream in such way
)> > that output stream does not contain sequence of
)> > two same bytes in a row?
)>
)> another way:
)>
)> you can see your stream as a big number in base 256,
)
) Streams may be infinite, (integer) numbers may not.
They can be unbounded, however. And if you view the first symbol
as the least significant, then there's no problem with that.
(Or you view it as a base-255 number between 0 and 1)
) For example - what would the stream consisting of nothing
) but hex AA map to? What's the lowest base-255 digit? Or
) the highest base-255 digit?
Some repeating sequence of symbols. I don't really feel like
calculating which exact symbols it will be.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| Phil Carmody 2004-05-12, 9:29 pm |
| Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:
> Salvador Fandiņo <salvafg@terra.es> writes:
>
>
> Streams may be infinite, (integer) numbers may not.
>
> For example - what would the stream consisting of nothing
> but hex AA map to?
ARGH! Argh argh argggggggh!
hex "AA"s plural. An infinite quantity thereof.
Ooops.
> What's the lowest base-255 digit? Or
> the highest base-255 digit?
--
1st bug in MS win2k source code found after 20 minutes: scanline.cpp
2nd and 3rd bug found after 10 more minutes: gethost.c
Both non-exploitable. (The 2nd/3rd ones might be, depending on the CRTL)
| |
| Phil Carmody 2004-05-12, 9:29 pm |
| Willem <willem@stack.nl> writes:
> Phil wrote:
> ) Salvador Fandiņo <salvafg@terra.es> writes:
> )
> )> Davor@Home wrote:
> )> > is it possible to transform data stream in such way
> )> > that output stream does not contain sequence of
> )> > two same bytes in a row?
> )>
> )> another way:
> )>
> )> you can see your stream as a big number in base 256,
That, to my mind, meant an integer.
> )
> ) Streams may be infinite, (integer) numbers may not.
>
> They can be unbounded, however.
An integer cannot be unbounded.
Integer N is bounded above by N+1, for example.
The _integers_ are not bounded, but there's a difference between
that set and its members.
> And if you view the first symbol
> as the least significant, then there's no problem with that.
>
> (Or you view it as a base-255 number between 0 and 1)
That would work. That's effectively the arithmetic coding route.
However, it's not what Salvador wrote, which is what I was
responding to.
An infinite stream cannot be viewed as an integer, unless it
falls into a set of zero density amongst the set of all streams.
> ) For example - what would the stream consisting of nothing
> ) but
[an infinite string of]
> ) hex AA map to? What's the lowest base-255 digit? Or
> ) the highest base-255 digit?
>
> Some repeating sequence of symbols. I don't really feel like
> calculating which exact symbols it will be.
The fraction can be calculated quite easily. You'll kick
yourself for not following through with it when you work
it out.
But as I said, it's not expressible as an integer.
If you try to shoe-horn it into pretending to be an integer,
the least significant base-255 digit would be the sum,
modulo 255, of the base-256 digits in the original stream,
which of course is undefined for arbitrary streams, only
for those whose representations become 0 after a finite
number of steps, which is a countable subset of an uncountable
set.
Phil
--
1st bug in MS win2k source code found after 20 minutes: scanline.cpp
2nd and 3rd bug found after 10 more minutes: gethost.c
Both non-exploitable. (The 2nd/3rd ones might be, depending on the CRTL)
| |
| Willem 2004-05-12, 9:29 pm |
| Phil wrote:
)> ) Streams may be infinite, (integer) numbers may not.
)>
)> They can be unbounded, however.
)
) An integer cannot be unbounded.
) Integer N is bounded above by N+1, for example.
) The _integers_ are not bounded, but there's a difference between
) that set and its members.
Well, in any case, you can start with the lowest-significant digits and
work your way up. If the stream is infinite, the number you're generating
will never be finished of course, but the transformation will work
nonetheless.
That's kinda what I tried to say with 'unbounded'.
) An infinite stream cannot be viewed as an integer, unless it
) falls into a set of zero density amongst the set of all streams.
Yes, but you can transform the mapping from base-256 to base-255 for finite
streams to a mapping for infinite streams quite easily, provided you view
the start of the streams as the least significant digits.
In other words: The algorithm(*) that maps base-256 to base-255 for
finite streams happens to work for infinite streams also. It's just
that you can't strictly view it as mapping from base to base anymore.
*) if it starts at the beginning of the stream, of course.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| Phil Carmody 2004-05-12, 9:29 pm |
| Willem <willem@stack.nl> writes:
> Phil wrote:
> )> ) Streams may be infinite, (integer) numbers may not.
> )>
> )> They can be unbounded, however.
> )
> ) An integer cannot be unbounded.
> ) Integer N is bounded above by N+1, for example.
> ) The _integers_ are not bounded, but there's a difference between
> ) that set and its members.
>
> Well, in any case, you can start with the lowest-significant digits and
> work your way up. If the stream is infinite, the number you're generating
> will never be finished of course, but the transformation will work
> nonetheless.
No it won't.
Is the lowest base-255 digit of base-256 < xAA, xAA, xAA, ...>
xAA, x55, or 0 ?
> That's kinda what I tried to say with 'unbounded'.
>
> ) An infinite stream cannot be viewed as an integer, unless it
> ) falls into a set of zero density amongst the set of all streams.
>
> Yes, but you can transform the mapping from base-256 to base-255 for finite
> streams to a mapping for infinite streams quite easily, provided you view
> the start of the streams as the least significant digits.
No you can't.
> In other words: The algorithm(*) that maps base-256 to base-255 for
> finite streams happens to work for infinite streams also.
No it doesn't.
0, x55 or xAA - which is it?
Or in other words - what is infinity modulo 3?
> It's just
> that you can't strictly view it as mapping from base to base anymore.
If you mean "you can't view them as big numbers in radix representation
any more" then you might get agreement, but the situation described
pertained to dealing with big numbers in radix representation.
> *) if it starts at the beginning of the stream, of course.
Remember - the lowest base-255 digit is the sum, modulo 255, of _all_
of the base-256 digits (as 256 == 1 mod 255).
In order to work out the lowest base-255 digit you must know
the sum of _all_ the base-256 digits. This can only be done if the
stream is only finitely non-zero.
Phil
--
1st bug in MS win2k source code found after 20 minutes: scanline.cpp
2nd and 3rd bug found after 10 more minutes: gethost.c
Both non-exploitable. (The 2nd/3rd ones might be, depending on the CRTL)
| |
| Brian Raiter 2004-05-12, 9:29 pm |
| >> For example - what would the stream consisting of nothing
>
> ARGH! Argh argh argggggggh!
>
> hex "AA"s plural. An infinite quantity thereof.
2/3, if we're allowed to assume that the stream is preceded by a
point.
b
| |
| Willem 2004-05-12, 9:29 pm |
| Phil wrote:
) No it won't.
)
) Is the lowest base-255 digit of base-256 < xAA, xAA, xAA, ...>
) xAA, x55, or 0 ?
Oh, right.. my mistake.
I was under the impression that you could transform between bases using
an algorithm that starts at one end and works towards the other, and
implicitly assuming that such an algorithm wouldn't have carries all the
way across the other end.
In other words, the carry bit threw me for a loop. Sorry.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
| |
| Salvador Fandiņo 2004-05-12, 9:29 pm |
| Phil Carmody wrote:
> Willem <willem@stack.nl> writes:
>=20
>=20
>=20
>=20
> That, to my mind, meant an integer.
>=20
>=20
>=20
>=20
> An integer cannot be unbounded.
> Integer N is bounded above by N+1, for example.
> The _integers_ are not bounded, but there's a difference between
> that set and its members.
>=20
>=20
>=20
>=20
> That would work. That's effectively the arithmetic coding route.
> However, it's not what Salvador wrote, which is what I was=20
> responding to.
there is not any difference in considering the stream as a=20
base-256 number between 0 and 1 . You will need an infinite=20
buffer for the computation anyway.
Consider the same problem but for bases 10 and 9,
0.9999999999999999... becomes 0.90000000000000....
but
0.999...(n)...9900... becomes 0.8888...????
and as n is not bounded, you need a buffer of unbounded size for=20
the computation.
But this is just the theory. In practice, you can break your=20
infinite stream in chunks (=3Dfinite streams) and code them using=20
this algorithm. You are going to lost some bits, but not too many=20
if you make your chunks of the right size: 1415Bytes (or 9593400,=20
or ...).
1415 256-digits are coded as 1416 255-digits
(1416*log(255)-1415*log(256))/1416*log(255) =3D
=3D 0.0012% bits "lost"
- Salvador
| |
| Salvador Fandiņo 2004-05-12, 9:29 pm |
| Salvador Fandi=F1o wrote:
> Consider the same problem but for bases 10 and 9,
>=20
> 0.9999999999999999... becomes 0.90000000000000....
>=20
> but
>=20
> 0.999...(n)...9900... becomes 0.8888...????
opps, I used the wrong numbers...
0.88888888888888888... becomes 0.80000000000
and
0.888...(n)...8800... becomes 0.7777...???
- Salvador
| |
| Phil Carmody 2004-05-12, 9:29 pm |
| Willem <willem@stack.nl> writes:
> Phil wrote:
> ) No it won't.
> )
> ) Is the lowest base-255 digit of base-256 < xAA, xAA, xAA, ...>
> ) xAA, x55, or 0 ?
>
> Oh, right.. my mistake.
> I was under the impression that you could transform between bases using
> an algorithm that starts at one end and works towards the other, and
> implicitly assuming that such an algorithm wouldn't have carries all the
> way across the other end.
> In other words, the carry bit threw me for a loop. Sorry.
No problem. As you yourself, and others later, have now pointed out,
the concept of base conversion is _entirely_ applicable to the problem
when viewing the thing as a bounded fraction (typically in the range
[0,1) ).
I was so stuck in a rut (hey, I was put there!) with the bignum
view, that it didn't click that the obvious (to me) arithmetic
coding scheme was in fact the obvious (to everyone but me)
base-conversion scheme.
So I too have had an "aha" <slaps forehead> moment during this
thread too! (Funny, I've spent more time doing base conversions
(in wacky rings, admittedly) than almost anything else recently,
I'm ashamed of myself for not making the connection immediately!)
Phil
--
1st bug in MS win2k source code found after 20 minutes: scanline.cpp
2nd and 3rd bug found after 10 more minutes: gethost.c
Both non-exploitable. (The 2nd/3rd ones might be, depending on the CRTL)
|
|
|
|
|