32/64 bit cc differences

[JohnF]

I'm getting a tiny-cum-microscopic, but nevertheless fatal,
difference in the behavior of the exact same C code compiled
on one 64-bit linux machine...
o dreamhost.com
uname -a Linux mothman 2.6.32.8-grsec-2.1.14-modsign-xeon-64 #2 SMP
Sat Mar 13 00:42:43 PST 2010 x86_64 GNU/Linux
cc --version cc (Debian 4.3.2-1.1) 4.3.2
versus two other 32-bit linuxes...
o panix.com
uname -a NetBSD panix3.panix.com 6.1.2 NetBSD 6.1.2 (PANIX-USER) #0:
Wed Oct 30 05:25:05 EDT 2013 i386
cc --version cc (NetBSD nb2 20110806) 4.5.3
o my own local box running slackware 14.0 32-bit
cc --version cc (GCC) 4.7.1

The code is an en/de-cryption utility forkosh.com/fm.zip,
which is way too many lines to ask anybody to look at.
But my own debugging is failing to identify where the
difference creeps in, and googling failed to help suggest
where to look more deeply.

Firstly, both executables "work", i.e., if you encrypt and
then decrypt, you get back the exact same original file.
But if you encrypt using the 32-bit executable, scp the
encrypted file to the 64-bit machine (md5's match) and then
decrypt, the result is exactly the same length and almost
identical except for about one byte in a thousand that doesn't
diff. Vice versa (encrypt on 64-bit, decrypt on 32) gives
the same behavior. (By the way, the 32-vs-64-bit encrypted files
are also ~one-in-a-thousand different, so both stages exhibit
this small problem.)
And I tried cc -m32 on the 64-bit machine, but there's
some stubs32.h that it's missing. So instead, I cc -static
on my own box, and that executable does work on the 64-bit
machine when run against files encrypted on either 32-bit box.
So the problem doesn't seem to be the 64-bit os, but rather
the cc executable, though I'm not 100% sure.

What I'm really finding weird is that ~one-byte-in-a-thousand
diff. The program uses several streams of random numbers
(generated by its own code) to xor bytes, permute bits, etc.
The slightest problem would garble up the data beyond belief.
Moreover, it's got a verbose flag, and I can see the streams
are identical. And everywhere else I've thought to look
seems okay, too, as far as I can tell.
So I'm asking about weird-ish 32/64-bit cc differences
that might give rise to this kind of behavior. Presumably,
there's some subtle bug that I'm failing to see in the code,
and which the output isn't helping me to zero in on. Thanks,
--
John Forkosh ( mailto: j...@f.com where j=john and f=forkosh )

[glen herrmannsfeldt]

JohnF <jo...@please.see.sig.for.email.com> wrote:
> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
> difference in the behavior of the exact same C code compiled
> on one 64-bit linux machine...
> o dreamhost.com

(snip)

> Firstly, both executables "work", i.e., if you encrypt and
> then decrypt, you get back the exact same original file.
> But if you encrypt using the 32-bit executable, scp the
> encrypted file to the 64-bit machine (md5's match) and then
> decrypt, the result is exactly the same length and almost
> identical except for about one byte in a thousand that doesn't
> diff. Vice versa (encrypt on 64-bit, decrypt on 32) gives
> the same behavior. (By the way, the 32-vs-64-bit encrypted files
> are also ~one-in-a-thousand different, so both stages exhibit
> this small problem.)

Some years ago, I wrote a JBIG2 coder. I could debug it
by sending the output, in the form of a PDF file, into
Adobe Reader.

As part of debugging, first I encoded a file of all zero bits.
(Well, the data part. It was a TIFF file with a bitmap image,
so all the image bits were zero.)

In many cases, as you note (and I snipped) once it goes wrong
it turns into random bits, but with the simpler file it tended
to go less wrong. It turns out that, at least in JBIG2, there
are enough things that don't happen very often that it can work
for a while before failing.

Then I made the data progressively more complicated.
(All ones, alternating 1/0 bytes, bits, various other simple
patterns.)

In your case, I would encrypt a file of all zeros, then
decrypt it while checking the output. As soon as a non-zero
byte comes out, stop. (Maybe put an if() inside to check
for it.)

Does the 64 bit system use 64 bit int? That could be enough
to confuse things. Or 64 bit long, where the program expects
a 32 bit long (or unsigned long)?

-- glen

[BartC]

"JohnF" <jo...@please.see.sig.for.email.com> wrote in message
news:laoglr$cig$1...@reader1.panix.com...

> I'm getting a tiny-cum-microscopic, but nevertheless fatal,

Fatal? I thought you said they worked.

> difference in the behavior of the exact same C code compiled
> on one 64-bit linux machine...

> What I'm really finding weird is that ~one-byte-in-a-thousand
> diff. The program uses several streams of random numbers
> (generated by its own code) to xor bytes, permute bits, etc.
> The slightest problem would garble up the data beyond belief.

Start with a known input file (eg. of all zeros as suggested), and of the
minimum size to show the problem (just over 1000 bytes for example).

Create a test to pick up the first difference, and make sure this difference
is repeatable.

Then try varying things: choose one stream of random numbers at a time for
example (disable the rest, or make them return zero), until files are the
same, then you can zero in on the bit that causes the problem. (Although the
difference might have moved to later in the file, or the problem is with the
interaction between particular bitpatterns from two streams.)

You might try also using, temporarily, specific widths for all integers,
instead of relying on whatever width 'int' happens to map to. However, if
int is 64-bits on one machine, then I think all intermediate results will be
widened to 64-bits, whatever you do.)

Print lots of diagnostics too, and compare them between the programs (ie.
all intermediate results). (I don't know how much output is likely for 1K of
output, or just enable output as you approach the point where you expect a
mismatch.) At the point where the output is different, some of those results
must be different too.

(You say you do this with 'verbose' output, but there must be a difference
at the point where the output changes, unless the problem is something to do
with file output itself: are you saying that you actually print each byte
that is written to the output, that this output is the same on both
machines, but when comparing the written files, that 1000th byte is
different?)

--
Bartc

[Richard Damon]

My guess would be that somewhere in the code "Undefined" or
"Implementation" defined behavior is happening, which the two compilers
are implementing differently. It might be an integer overflow or
something similar. Note that some types will have different sizes
between the two implementations.

It is also possible that some behavior is dependent in a corner case on
implementation defined values, like the maximum value of an int.

[Siri Cruz]

In article <laoglr$cig$1...@reader1.panix.com>,

JohnF <jo...@please.see.sig.for.email.com> wrote:

> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
> difference in the behavior of the exact same C code compiled
> on one 64-bit linux machine...

Problems I found when I tried compiling from 32 bit macosx to 64 bit:

(1) var args arguments integer and pointer constants like 0, 1, 2 that were
stilled compiled into 32 bit values, but with like va_arg(argv, long int) that
now expected a 64 bit argument.

(2) Uninitialised variables that had been zeroed were now random values.

(3) Linking with differently compiled objects.

(4) Exposing bad assumptions about alignment and byte order from casts and
unions.

Also going from ppc to i386:

(5) Procedure frame allocation changed to block frame.

Also 32 bit and 64 bit were different macosx version (10.6 vs 10.8) with
differences besides word size, like randomised stack addresses that broke the
garbage collector.

--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted.
'I desire mercy, not sacrifice.'

[JohnF]

Thanks, Glen. It's your "as soon as" that's a problem in my case.
I'd already tried a binary zero file, and various other test cases.
For encrypting, the program fread()'s the input file in randomly-sized
blocks, processing each block separately. It first adds a random number
of noise bytes (which can be set to 0 and which I tried),
then randomly xor or xnor's each data byte with a random byte from
your key, and finally randomly permutes the bits of the entire block
(typically a many-thousand-bit permutation). Decrypting reverses
the procedure.
The "as soon as" problem is because blocks are big garbled
messes until every step is performed on the entire block.
You can't get byte after byte of decrypted stuff. But you can
turn off some things, which I did try, but which failed to identify
the source of the problem (as far as I could tell). You can also
turn off everything by giving it no key, in which case it just
copies infile->outfile. And, yeah, that works on both 32- and 64-bit
compiled executables (that would've been too easy:).
Of course, I can modify the program to turn off stuff more
"slowly", and I'm pretty sure that'll eventually zero in on the
problem. But it's a big pain to do that properly, e.g., the random
number streams have to be kept in sync reversibly, so that
encrypted stuff can be decrypted.
So I'm trying to figure out smart guesses what to try first,
before wasting lots of time trying things that I should know
(if I were smarter) can't be problems. And I posted the question
hoping someone had tripped over similar problems. It's not
so much "try a file with all binary zeroes" that I need to hear;
it's more like "these are the operations/constructions/etc that
are likely to go unnoticed on 32-bit and then behave differently
on 64-bit". See below...

> Does the 64 bit system use 64 bit int? That could be enough
> to confuse things. Or 64 bit long, where the program expects
> a 32 bit long (or unsigned long)? -- glen

Yeah, that's the kind of thing that could "go unnoticed and
then behave differently". And there are indeed a couple of
long long's (and %lld debugging printf's), in the program's rng,
but I've checked all that very, very carefully.
What I had also been thinking was that my xor/xnor's were
getting fouled up by strangely different endian-ness behavior,
i.e., which byte of i contains c in unsigned char c; int i = (int)c;
for 32- versus 64-bit, and how does that affect ^,~ operations?
But I checked that with a little offline test program,
and think (maybe 85% confidence) it's okay. And I'd think
it should mess up way more often if not okay.

The code's supposed to be quite portable, and was originally
checked on intel linux, netbsd, freebsd, ms windows, and on
VAX and alpha OpenVMS. It always generated identical encrypted
files...until now.

[Ben Bacarisse]

JohnF <jo...@please.see.sig.for.email.com> writes:
<snip>

> The code is an en/de-cryption utility forkosh.com/fm.zip,
> which is way too many lines to ask anybody to look at.

Well, it's only about 1100 lines in one file, and about 740 that are not
comment lines. Unfortunately it has inconsistent (and odd) spacing and
indentation. It made my head hurt reading it!

There are signs that it's not written by someone who knows C well --
some odd idioms, unnecessary casts, not using prototype declarations,
using signed types for bit operations... These things mean it's going
to be harder work that one might hope. You'll need to decide if the
pay-off is worth it.

<snip>

> What I'm really finding weird is that ~one-byte-in-a-thousand
> diff. The program uses several streams of random numbers
> (generated by its own code) to xor bytes, permute bits, etc.
> The slightest problem would garble up the data beyond belief.

Not if the error is at a late stage in the decryption -- say some sort
of final permutation. The program works in blocks, so if it has a block
size of 1000 bytes, you might be seeing and entirely predictable error
that occurs every time.

<snip>
--
Ben.

[JohnF]

BartC <b...@freeuk.com> wrote:
> "JohnF" <jo...@please.see.sig.for.email.com> wrote in message
> news:laoglr$cig$1...@reader1.panix.com...
>> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
>
> Fatal? I thought you said they worked.

They're separately consistent -- each correctly decrypts what
it encrypts, but not what the other encrypts.

>> difference in the behavior of the exact same C code compiled
>> on one 64-bit linux machine...
>
>> What I'm really finding weird is that ~one-byte-in-a-thousand
>> diff. The program uses several streams of random numbers
>> (generated by its own code) to xor bytes, permute bits, etc.
>> The slightest problem would garble up the data beyond belief.
>
> Start with a known input file (eg. of all zeros as suggested), and of the
> minimum size to show the problem (just over 1000 bytes for example).
>
> Create a test to pick up the first difference, and make sure this difference
> is repeatable.

Sure, already done.

> Then try varying things: choose one stream of random numbers at a time for
> example (disable the rest, or make them return zero), until files are the
> same, then you can zero in on the bit that causes the problem.

Yes, this has to eventually work. But, as pointed out to Glen,
I already tried turning off the things that were easy to turn off,
without finding the problem. What I'm looking for now, before messing
with lots of code, is suggestions about esoteric things that might
behave differently on 32- vs 64-bit. That'll suggest what code
to mess with first. Let me cut-and-paste from followup to Glen
one such thing I'd tried before posting,

"What I had also been thinking was that my xor/xnor's were
getting fouled up by strangely different endian-ness behavior,
i.e., which byte of i contains c in unsigned char c; int i = (int)c;
for 32- versus 64-bit, and how does that affect ^,~ operations?
But I checked that with a little offline test program,
and think (maybe 85% confidence) it's okay. And I'd think
it should mess up way more often if not okay."

So that's the kind of thing I'm guessing must be wrong,
but haven't been able to think of anything further along
those lines which would suggest how to best proceed.

> (Although the
> difference might have moved to later in the file, or the problem is with the
> interaction between particular bitpatterns from two streams.)
>
> You might try also using, temporarily, specific widths for all integers,
> instead of relying on whatever width 'int' happens to map to. However, if
> int is 64-bits on one machine, then I think all intermediate results will be
> widened to 64-bits, whatever you do.)

Yeah, I didn't mention that I'd also tried -m32-bit on the 64-bit box,
but that compiler (--version is cc (Debian 4.3.2-1.1) 4.3.2) said
cc1: error: unrecognized command line option "-m32-bit"
and man cc isn't on that machine.

> Print lots of diagnostics too, and compare them between the programs (ie.
> all intermediate results). (I don't know how much output is likely for 1K of
> output, or just enable output as you approach the point where you expect a
> mismatch.) At the point where the output is different, some of those results
> must be different too.

Yes, something must be different. But, as in followup to Glen, "approach"
isn't quite appropriate since an entire block must be completely
processed before any of the bytes within it make sense.
And, yeah, your implied guess that there's too many internal/intermediate
calculations to output them all is correct. As usual, it's got to
be a kind of "binary search" where and what to printf.

> (You say you do this with 'verbose' output, but there must be a difference
> at the point where the output changes, unless the problem is something to do
> with file output itself: are you saying that you actually print each byte
> that is written to the output, that this output is the same on both
> machines, but when comparing the written files, that 1000th byte is
> different?)

Yeah, exactly, I prepared a suite of test input files (including
several all binary zeroes files of different lengths), and it's roughly
(but not exactly) every 1000th byte of output that's different. Weirdly,
a test input file with 2000 0's versus one with 3000 0's has the first
output mess-up at different places. And in both cases, the program's
first random block size was 6159 bytes (because I used the same key),
so it read both files all at once. That is, the problem isn't at
block boundaries (which would've been way too easy:).

[JohnF]

Yeah, that's almost certainly what's happening. I'm calling
it a "bug" (in my program) because the code was meant to be
portable, and was intentionally written to work on any architecture,
relying only on standard C semantics. But I apparently didn't write
it intentionally enough, and missed something.

> It might be an integer overflow

But not that, I don't think.

> or something similar.
Yeah, that's the one.

> Note that some types will have different sizes
> between the two implementations.
> It is also possible that some behavior is dependent in a corner case on
> implementation defined values, like the maximum value of an int.

[Robert Wessel]

I agree that's could be a useful approach if he's really stumped. You
could drop a printf* of the stored value after every assignment (the
code isn't that big, after all), and then diff the results, the spot
where things diverge should be a good clue.

Another suggestion, and perhaps an easier one, is to lint the thing
severely. That may well highlight some portability issues. Gimpel
has an online demo of their lint product, if the OP can reduce it to
a single text file he should be able to just paste it in there.


*a good use of a macro and __LINE__. Perhaps something like:

#define DBG_VAL(name, val, fmt) printf(__line__ ":" name "=" fmt "\n",
val);

And some wrappers to make that simpler to use in common cases (say
ints).

[JohnF]

Siri Cruz <chine...@yahoo.com> wrote:
> JohnF <jo...@please.see.sig.for.email.com> wrote:
>
>> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
>> difference in the behavior of the exact same C code compiled
>> on one 64-bit linux machine...
>
> Problems I found when I tried compiling from 32 bit macosx to 64 bit:

Thanks, Siri, these are exactly the kinds of things I was
hoping to hear about. Somewhere or other I've made that
kind of mistake.

> (1) var args arguments integer and pointer constants like 0, 1, 2 that were
> stilled compiled into 32 bit values, but with like va_arg(argv, long int)
> that now expected a 64 bit argument.

No variable argument lists, so not that mistake.

> (2) Uninitialised variables that had been zeroed were now random values.

I don't think I leave any uninitialized variables hanging,
but could be. In that case it's not even a 32- vs 64-bit problem,
per se, just that the 64-bit compiler isn't zeroing memory like the others.

> (3) Linking with differently compiled objects.

Just one module containing all funcs.

> (4) Exposing bad assumptions about alignment and byte order from casts
> and unions.

No unions, but some kind of alignment issue might be possible.

> Also going from ppc to i386:
>
> (5) Procedure frame allocation changed to block frame.
>
> Also 32 bit and 64 bit were different macosx version (10.6 vs 10.8) with
> differences besides word size, like randomised stack addresses that broke
> the garbage collector.

Those not problems, but I will double-check your preceding suggestions.
Thanks again,

[Richard]

Well, that helps. I thought there might be an issue with the C code
too...

--
"Avoid hyperbole at all costs, its the most destructive argument on
the planet" - Mark McIntyre in comp.lang.c

[JohnF]

Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
> JohnF <jo...@please.see.sig.for.email.com> writes:
> <snip>
>> The code is an en/de-cryption utility forkosh.com/fm.zip,
>> which is way too many lines to ask anybody to look at.
>
> Well, it's only about 1100 lines in one file, and about 740 that are not
> comment lines. Unfortunately it has inconsistent (and odd) spacing and
> indentation. It made my head hurt reading it!

Thanks, Ben, and sorry about that. I pretty much figured >100 lines
was too much to ask anybody to read.

> There are signs that it's not written by someone who knows C well --
> some odd idioms, unnecessary casts, not using prototype declarations,
> using signed types for bit operations... These things mean it's going
> to be harder work that one might hope. You'll need to decide if the
> pay-off is worth it.

From the "Revision history" comment near top, note that first version
was written in 1988, ported from an even earlier program.
Your "signed types for bit operations" is indeed the one problem
I'd actually worried about (not that the others aren't problems,
but unlikely to be causing odd observed behavior), and which
I actually checked with small standalone test program, as noted
in preceding followup. But that particular problem is easy enough
to fix (I know exactly what you're referring to in xcryptstr),
and I'll do that (and kick myself if it fixes the problem).

> <snip>
>> What I'm really finding weird is that ~one-byte-in-a-thousand
>> diff. The program uses several streams of random numbers
>> (generated by its own code) to xor bytes, permute bits, etc.
>> The slightest problem would garble up the data beyond belief.
>
> Not if the error is at a late stage in the decryption -- say some sort
> of final permutation.

Permutation will mess up all-or-nothing, as far as I can tell.
It's xcryptstr with the xor/xnor's that (as far as I can tell, again)
is the likely culprit along this line of thought. But I think
I checked that, and I think the error frequency would be greater
if it were messing up. But I could be twice wrong (that would
be the "kicking" part:).

> The program works in blocks, so if it has a block
> size of 1000 bytes, you might be seeing and entirely predictable error
> that occurs every time.

As pointed out in preceding followup, I'd eliminated the possibility
of block boundary errors. But it had indeed crossed my mind as the
one obvious explanation for the observed byte error distribution.

P.S. I'm amazed you read the code so fast and in enough detail
with enough understanding to pick up the info for your remarks.
Scary. Thanks again,

[Ben Bacarisse]

JohnF <jo...@please.see.sig.for.email.com> writes:
<snip>

>> (2) Uninitialised variables that had been zeroed were now random values.
> I don't think I leave any uninitialized variables hanging,
> but could be. In that case it's not even a 32- vs 64-bit problem,
> per se, just that the 64-bit compiler isn't zeroing memory like the
> others.

There is a very useful program called valgrind. You will want to strew
scented petals before the feet of those who wrote it.

However, it does not report the use of any initialised data so it's
value here is negative. Of course, that was only one example run. I'd
be tempted to use it for every run until the issue is fixed.

<snip>
--
Ben.

[Ben Bacarisse]

Actually I was thinking about the bit getting and setting macros myself.
Also, check that the shift amount is never equal to the bit width. The
fact that this is not defined (even for unsigned types) surprises some
people. One way to do this is to add an assert to them.

The other thing I'd do is to check all the casts and remove those that
are not needed. They can mask interesting and useful compiler warnings.
(You are asking for lots of warnings, I hope.)

<snip>

> P.S. I'm amazed you read the code so fast and in enough detail
> with enough understanding to pick up the info for your remarks.
> Scary. Thanks again,

I once had a job which was almost entirely porting C code from one
system to another very peculiar one. The result is that some (sadly not
all) portability problems leap out at me.

--
Ben.

[BartC]

"JohnF" <jo...@please.see.sig.for.email.com> wrote in message

news:laoua0$r0m$1...@reader1.panix.com...

> BartC <b...@freeuk.com> wrote:
>> "JohnF" <jo...@please.see.sig.for.email.com> wrote in message

>> You might try also using, temporarily, specific widths for all integers,
>> instead of relying on whatever width 'int' happens to map to. However, if
>> int is 64-bits on one machine, then I think all intermediate results will
>> be
>> widened to 64-bits, whatever you do.)
>
> Yeah, I didn't mention that I'd also tried -m32-bit on the 64-bit box,
> but that compiler (--version is cc (Debian 4.3.2-1.1) 4.3.2) said
> cc1: error: unrecognized command line option "-m32-bit"
> and man cc isn't on that machine.

How big are int, long and long long on your machines?

I seem to remember that gcc 'long' was 32-bit under Windows, and 64-bit
under Linux. (If you expect long to be 64-bits, and ever want to run under
Windows, you might want to upgrade the type.)

(I've looked at your code; I've no idea what the problem might be, but if
you're porting from an int=32, long=64 implementation to an int=64, long=64
one, I'm surprised you haven't got bigger differences. Certainly my own code
would have a load of problems!)

--
Bartc

[James Kuyper]

On 01/10/2014 08:21 AM, JohnF wrote:
> glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>> JohnF <jo...@please.see.sig.for.email.com> wrote:

> For encrypting, the program fread()'s the input file in randomly-sized
> blocks, processing each block separately. It first adds a random number
> of noise bytes (which can be set to 0 and which I tried),
> then randomly xor or xnor's each data byte with a random byte from
> your key, and finally randomly permutes the bits of the entire block
> (typically a many-thousand-bit permutation). Decrypting reverses
> the procedure.

...

> Of course, I can modify the program to turn off stuff more
> "slowly", and I'm pretty sure that'll eventually zero in on the
> problem. But it's a big pain to do that properly, e.g., the random
> number streams have to be kept in sync reversibly, so that
> encrypted stuff can be decrypted.

The random numbers in your program make it difficult to debug, because
the behavior can be different each time it's run. For debugging
purposes, you should modify the code to use a fixed seed for your random
number generator, so that it generates exactly the same random numbers
each time it is run. Make sure that the particular seed you use is one
that will reproduce the problem!
One possible issue is that the random number generators on the two
systems might be different. You might need to write your own, just to
make sure it generates the same sequence every time, on both systems. It
doesn't have to be a very sophisticated one, so long as it does
reproducibly duplicate the problem you're seeing.

[Aleksandar Kuktin]

On Fri, 10 Jan 2014 10:05:47 +0000, JohnF wrote:

> Firstly, both executables "work", i.e., if you encrypt and then decrypt,
> you get back the exact same original file.
> But if you encrypt using the 32-bit executable, scp the encrypted file
> to the 64-bit machine (md5's match) and then decrypt, the result is
> exactly the same length and almost identical except for about one byte
> in a thousand that doesn't diff. Vice versa (encrypt on 64-bit, decrypt
> on 32) gives the same behavior. (By the way, the 32-vs-64-bit encrypted
> files are also ~one-in-a-thousand different, so both stages exhibit this
> small problem.)

Wait, I don't understand this.

Correct me if I'm wrong:
1. same input file;
2. output of 32-bit executable and of 64-bit executable are bit-for-bit
identical;
3. output of executable, when decrypted by same executable that outputted
it, is bit-for-bit identical to the input;
4. output of 32-bit executable, when decrypted on 64-bit produces wrong
output;
5. output of 64-bit executable, when decrypted on 32-bit produces wrong
output.

Obviously, this can not be.

[James Kuyper]

My understanding of what he's saying (I could be mistaken) is that
input => 32-bit executable in encrypt mode => encrypted1 => 32-bit
executable in decrypt mode=> output1

input => 64-bit executable in encrypt mode => encrypted2 => 64-bit
executable in decrypt mode => output1

output1 is identical to input, for both runs, but encrypted1 differs
from encrypted2. As a result:

input => 32-bit executable in encrypt mode => encrypted1 => 64-bit
executable in decrypt mode => output2

input => 64-bit executable in encrypt mode => encrypted2 => 32-bit
executable in decrypt mode => output3

Neither output2 nor output3 is the same as output1 - but only one byte
in a thousand is different.

[Keith Thompson]

Aleksandar Kuktin <aku...@gmail.com> writes:
> On Fri, 10 Jan 2014 10:05:47 +0000, JohnF wrote:
>> Firstly, both executables "work", i.e., if you encrypt and then decrypt,
>> you get back the exact same original file.
>> But if you encrypt using the 32-bit executable, scp the encrypted file
>> to the 64-bit machine (md5's match) and then decrypt, the result is
>> exactly the same length and almost identical except for about one byte
>> in a thousand that doesn't diff. Vice versa (encrypt on 64-bit, decrypt
>> on 32) gives the same behavior. (By the way, the 32-vs-64-bit encrypted
>> files are also ~one-in-a-thousand different, so both stages exhibit this
>> small problem.)
>
> Wait, I don't understand this.
>
> Correct me if I'm wrong:
> 1. same input file;
> 2. output of 32-bit executable and of 64-bit executable are bit-for-bit
> identical;

I don't believe that's what he said.

On both 32-bit and 64-bit systems, encrypting a file *and then
decrypting it* yields an identical copy of the original file.
But the content of the encrypted file can vary (probably even from
one run to the next, since the program makes heavy use of random
numbers).

So a 32-bit encrypted file and a 64-bit encrypted file, from the
same input, will differ -- and decrypting a 32-bit encrypted file
using the 64-bit decryption program, or vice versa, yields output
that's *slightly* different from the original input.

JohnF, have I summarized the behavior correctly?

You say "about one byte in a thousand". Is there any pattern to
where the incorect bytes appear in the output? For example, if
the last byte of each 1024-byte block were incorrect, that would
be interesting. If it's seemingly random and varies from one run
to the next, that would also be interesting.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Stephen Sprunk]

On 10-Jan-14 07:21, JohnF wrote:
> The code's supposed to be quite portable, and was originally
> checked on intel linux, netbsd, freebsd, ms windows, and on
> VAX and alpha OpenVMS. It always generated identical encrypted
> files...until now.

Are all of those systems ILP32, or is the Alpha one ILP64? (I've never
used OpenVMS.) Have you tried it on Win64, which is IL32LLP64, or just
Win32?

Linux/x86-64 is I32LP64, so if that's the first such system you've
ported to, that may indicate where the problem lies. If your code works
on ILP64 systems, type problems seem unlikely, but you could still have
int/long mismatches that wouldn't show up there--or on IL32LLP64.

Also, you're using three different versions of GCC; it's possible that
one of them has a bug (or "feature") that's triggered by some UB in your
code and results in slight output changes. I'd highly suggest using the
same version on all your systems, if possible, to eliminate that as a
potential source of differences.

Aside: Why roll your own encryption algorithm rather than use a proven,
off-the-shelf algorithm, e.g. AES? Depending on OpenSSL's libcrypto is
pretty standard these days; no sense reinventing the square wheel.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

[osmium]

As a bystander to this thread, that sounds like a Really Really Good Idea.

[Stephen Sprunk]

On 10-Jan-14 11:29, Keith Thompson wrote:
> You say "about one byte in a thousand". Is there any pattern to
> where the incorect bytes appear in the output? For example, if
> the last byte of each 1024-byte block were incorrect, that would
> be interesting. If it's seemingly random and varies from one run
> to the next, that would also be interesting.

My first thought when seeing "one byte error every $blocksize" is that
there's an off-by-one error reading/modifying some buffer, but I can't
think of how porting between 32- and 64-bit variants of essentially the
same implementation would trigger such; it should always be there.

[Eric Sosman]

On 1/10/2014 5:05 AM, JohnF wrote:
> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
> difference in the behavior of the exact same C code compiled
> on one 64-bit linux machine...

I concur with Ben Bacarisse's assessment of the code's
readability; my head hurts, too! But I toughed it out with
Tylenol long enough to notice one possible source of trouble:
Your pseudo-random number generator produces `float' values.
Even if the internal mechanics of the generator are accurately
reproduced on all systems, the actual values used in subsequent
computations might not be. The C Standard gives implementations
some freedom in floating-point calculation, in particular:

"Except for assignment and cast (which remove all extra
range and precision), the values yielded by operators with
floating operands and values subject to the usual arithmetic
conversions and of floating constants are evaluated to a
format whose range and precision may be greater than
required by the type. [...]" -- 5.2.4.2.2p9

So: The computations involving the `float' numbers you generate
might come out differently on different machines, even if you
manage to generate exactly the same `float' numbers. One machine
could use `float' precision, another could use `double', yet
another might use `long double' or even some hardware-internal
precision not directly accessible from C. The upshot is that a
low-order bit might round differently every now and again. (And
because of the way your program operates, there's a decent chance
that the damage could be affect only a single block and leave any
subsequent blocks intact.)

I'm not saying this *does* happen, only that it might. Unless
you find some other smoking gun -- or even if you do! -- I'd suggest
eliminating all floating-point calculation from the program. Use
a purely-integer PRNG, and use purely-integer arithmetic on what
it generates.

--
Eric Sosman
eso...@comcast-dot-net.invalid

[Mikko Rauhala]

On Fri, 10 Jan 2014 17:54:12 -0500, Eric Sosman
<eso...@comcast-dot-net.invalid> wrote:
> On 1/10/2014 5:05 AM, JohnF wrote:
>> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
>> difference in the behavior of the exact same C code compiled
>> on one 64-bit linux machine...
>
> I concur with Ben Bacarisse's assessment of the code's
> readability; my head hurts, too! But I toughed it out with
> Tylenol long enough to notice one possible source of trouble:
> Your pseudo-random number generator produces `float' values.

Good catch. This is definitely something that might cause the
problem. To add some detail, x86 FPUs use 80-bit extended
precision internally, while x86-64 has deprecated (or altogether
disabled for long mode, not sure) the old FPU interface. x86-64
compilers use SSE2 as the baseline for float functionality these
days, and _there_ the precision is standard 64-bit double.

--
Mikko Rauhala - m...@iki.fi - <URL:http://www.iki.fi/mjr/>

[glen herrmannsfeldt]

Eric Sosman <eso...@comcast-dot-net.invalid> wrote:
> On 1/10/2014 5:05 AM, JohnF wrote:
>> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
>> difference in the behavior of the exact same C code compiled
>> on one 64-bit linux machine...

> I concur with Ben Bacarisse's assessment of the code's
> readability; my head hurts, too! But I toughed it out with
> Tylenol long enough to notice one possible source of trouble:
> Your pseudo-random number generator produces `float' values.
> Even if the internal mechanics of the generator are accurately
> reproduced on all systems, the actual values used in subsequent
> computations might not be. The C Standard gives implementations
> some freedom in floating-point calculation, in particular:

I hadn't looked at it at all before my post. Yes, don't use float
if you want predictable results. Knuth has written that floating
point shouldn't be used for financial or typesetting. Seems to me
that it shouldn't be used for encryption, either.

The other one that I thought about that comes up just often
enough is bit shifts greater than or equal to the word size.

Many machines treat shift modulo the width of the word, such
that shifting a 32 bit int 32 bits doesn't shift at all.
On a 64 bit system, with a 64 bit int, it would shift.

-- glen

[Keith Thompson]

glen herrmannsfeldt <g...@ugcs.caltech.edu> writes:
[...]

> Many machines treat shift modulo the width of the word, such
> that shifting a 32 bit int 32 bits doesn't shift at all.
> On a 64 bit system, with a 64 bit int, it would shift.

Which is why such shifts have undefined behavior (depending on the width
of the left operand, not necessarily on the width of a "word"):

N1570 6.5.7p3:
The integer promotions are performed on each of the operands. The
type of the result is that of the promoted left operand.
If the value of the right operand is negative or is greater
than or equal to the width of the promoted left operand, the
behavior is undefined.

[Ben Bacarisse]

Mikko Rauhala <m...@iki.fi> writes:

> On Fri, 10 Jan 2014 17:54:12 -0500, Eric Sosman
> <eso...@comcast-dot-net.invalid> wrote:
>> On 1/10/2014 5:05 AM, JohnF wrote:
>>> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
>>> difference in the behavior of the exact same C code compiled
>>> on one 64-bit linux machine...
>>
>> I concur with Ben Bacarisse's assessment of the code's
>> readability; my head hurts, too! But I toughed it out with
>> Tylenol long enough to notice one possible source of trouble:
>> Your pseudo-random number generator produces `float' values.
>
> Good catch. This is definitely something that might cause the
> problem.

Yes, good spot. It might not be a problem though because the program
scatters "random" data about which is then filtered out on decryption.
FP differences will just add another dimension to the "randomness".
However, if the RNG is also used for deterministic but chaotic data in
the heart of the algorithm then, yes, there will be trouble ahead.

<snip>
--
Ben.

[glen herrmannsfeldt]

Keith Thompson <ks...@mib.org> wrote:
> glen herrmannsfeldt <g...@ugcs.caltech.edu> writes:
> [...]
>> Many machines treat shift modulo the width of the word, such
>> that shifting a 32 bit int 32 bits doesn't shift at all.
>> On a 64 bit system, with a 64 bit int, it would shift.

> Which is why such shifts have undefined behavior (depending on the width
> of the left operand, not necessarily on the width of a "word"):

If you define "word" as the size of the left operand, then it is word,
but yes. Well, after the appropriate promotions.

> N1570 6.5.7p3:
> The integer promotions are performed on each of the operands. The
> type of the result is that of the promoted left operand.
> If the value of the right operand is negative or is greater
> than or equal to the width of the promoted left operand, the
> behavior is undefined.

In the development of the Hercules IBM mainframe emulator, when
OS/360 was almost, but not quite, running, I remembered that S/360
does shifts (32 and 64 bit) modulo 64. As well as I remember, without
looking at the code I figured out that might be a problem.

-- glen

-- glen

[Kaz Kylheku]

Other undefined behaviors can happen "modulo". For instance, suppose that a
structure contains some small near the beginning and so statically addressed
entries in this array, like foo.a[3] can be addressed using some displaced
addressing mode where the displacement is a small field in the instruction
opcode, say 6 bits wide or whatever. Then foo.a[257] could be reduced to 1
(modulo 64): just stuffed into the opcode and truncated. "Undefined behavior"
allows that.

[Gordon Burditt]

> Firstly, both executables "work", i.e., if you encrypt and
> then decrypt, you get back the exact same original file.
> But if you encrypt using the 32-bit executable, scp the
> encrypted file to the 64-bit machine (md5's match) and then
> decrypt, the result is exactly the same length and almost
> identical except for about one byte in a thousand that doesn't
> diff. Vice versa (encrypt on 64-bit, decrypt on 32) gives
> the same behavior. (By the way, the 32-vs-64-bit encrypted files
> are also ~one-in-a-thousand different, so both stages exhibit
> this small problem.)

> And I tried cc -m32 on the 64-bit machine, but there's
> some stubs32.h that it's missing. So instead, I cc -static
> on my own box, and that executable does work on the 64-bit
> machine when run against files encrypted on either 32-bit box.
> So the problem doesn't seem to be the 64-bit os, but rather
> the cc executable, though I'm not 100% sure.

Does your encryption algorithm use the same block size for both
32-bit and 64-bit encryption? For example, you have a loop that
takes a chunk of the data, encrypts it, and then loops, but on the
32-bit machine, it does 4 (8-bit) bytes in a chunk, and it does 8
(8-bit) bytes in a chunk on the 64-bit machine.

In that situation, doing 4 bytes at a time vs. 8 bytes at a time
may *NOT* be equivalent if it's possible to get a carry between the
lower 32-bit half and the upper 32-bit half. On the 32-bit machine,
that carry would be dropped. On the 64-bit machine, it would get
passed through. For some algorithms (such as those that involve
reversing bit order end-to-end), it should be blatantly obvious
that they are not equivalent. For others, the two may be equivalent
except under an unusual condition.

Ok, I'm reaching a lot here since I haven't seen the code.

What happens if the length of the data to be encrypted is an odd
multiple of 4? Or does a padding algorithm prevent that from ever
happening?

What is your plaintext now? It wouldn't happen to be UTF-8 that's
mostly ASCII but maybe one in a thousand characters has the high
bit set for an accented letter or Microsoft "smart quote"? What
happens if your plaintext is Chinese encoded in UTF-8? (That is,
*ALL* of the characters have the 0x80 bit set).



Some general trouble spots to look for:

Dereferencing a pointer to a 32-bit or 64-bit buffer to load or
store a bunch of characters, *EVEN IF* you make sure that the buffer
is aligned on a 32- or 64-bit boundary.

Endianness differences between the machines (probably not an issue
here).

The use of signed variables to hold encrypted data may cause problems
(e.g. x >> n replicating the sign bit rather than shifting in zero,
unexpected overflow traps, etc.) Also, if you store individual
bytes in a signed char, sign extension of bytes may cause problems.
I recommend using unsigned variables, whether bytes or integers,
to hold plaintext, ciphertext, key, random bytes, or combinations
of these. Things like loop counters and the remaining text length
are a different situation.

x << 32 or x >> 32 is defined if x is 64 bits wide, but not if x
is 32 bits wide.

64-bit calculations can store extra bits (on the high-order end)
for intermediate calculations. An operation like "multiply by 2,
then divide by 3" may have to be re-written "multiply by 2, AND
with 0xffffffff, then divide by 3" for 32-bit calculations run on
a 64-bit machine. (However, you only see a difference if the
0x80000000 bit was on.)



It may be a good idea to temporarily cripple your random number
generators to make them put out something blatantly predictble,
like 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 0a, 0b, ... . Or
perhaps 55, 55, 55, 55, 55, ... . If the problem doesn't go away,
you should have an easier time debugging with more predictable data.
If the problem DOES go away, perhaps you now have a clue to make
a pattern that causes the problem all the time.

As someone else mentioned, use of floating point in a random number
generator may cause issues, especially carrying of extra precision
in unexpected places, combined with rounding modes.

Among other possible problems, the default initial rounding mode
for floating point may be determined by the OS (NOT the C library
or compiled code). (I do recall someone discovering that this could
vary between different OS platforms, I think including Windows vs.
Windows (maybe XP vs. Windows 7) using the bit-for-bit same executable
on both. This can cause baffling problems of the exact same
executable running differently on different systems.

[JohnF]

James Kuyper <james...@verizon.net> wrote:
> On 01/10/2014 08:21 AM, JohnF wrote:
>> glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>>> JohnF <jo...@please.see.sig.for.email.com> wrote:
>
>> For encrypting, the program fread()'s the input file in randomly-sized
>> blocks, processing each block separately. It first adds a random number
>> of noise bytes (which can be set to 0 and which I tried),
>> then randomly xor or xnor's each data byte with a random byte from
>> your key, and finally randomly permutes the bits of the entire block
>> (typically a many-thousand-bit permutation). Decrypting reverses
>> the procedure.
> ...
>> Of course, I can modify the program to turn off stuff more
>> "slowly", and I'm pretty sure that'll eventually zero in on the
>> problem. But it's a big pain to do that properly, e.g., the random
>> number streams have to be kept in sync reversibly, so that
>> encrypted stuff can be decrypted.
>
> The random numbers in your program make it difficult to debug, because
> the behavior can be different each time it's run.

Not really. Seeds are generated from hash-like functions of user's
input key(s). How could it later decrypt what it had previously
encrypted if seeds were generated differently every run?
But I did find the problem (see subsequent followup),
and you're closer than you might think based on preceding remark.

> For debugging
> purposes, you should modify the code to use a fixed seed for your random
> number generator, so that it generates exactly the same random numbers
> each time it is run. Make sure that the particular seed you use is one
> that will reproduce the problem!
> One possible issue is that the random number generators on the two
> systems might be different. You might need to write your own, just to
> make sure it generates the same sequence every time, on both systems. It
> doesn't have to be a very sophisticated one, so long as it does
> reproducibly duplicate the problem you're seeing.

[JohnF]

BartC <b...@freeuk.com> wrote:
> "JohnF" <jo...@please.see.sig.for.email.com> wrote in message
> news:laoua0$r0m$1...@reader1.panix.com...
>> BartC <b...@freeuk.com> wrote:
>>> "JohnF" <jo...@please.see.sig.for.email.com> wrote in message
>
>>> You might try also using, temporarily, specific widths for all integers,
>>> instead of relying on whatever width 'int' happens to map to. However, if
>>> int is 64-bits on one machine, then I think all intermediate results will
>>> be
>>> widened to 64-bits, whatever you do.)
>>
>> Yeah, I didn't mention that I'd also tried -m32-bit on the 64-bit box,
>> but that compiler (--version is cc (Debian 4.3.2-1.1) 4.3.2) said
>> cc1: error: unrecognized command line option "-m32-bit"
>> and man cc isn't on that machine.
>
> How big are int, long and long long on your machines?

Yeah, I suppose I should put a verbose/debugging printf
for sizeof(this),sizeof(that),sizeof(the_other_thing),etc,
just to easily and immediately see what's going on in
every environment I run it on.

> I seem to remember that gcc 'long' was 32-bit under Windows, and 64-bit
> under Linux. (If you expect long to be 64-bits, and ever want to run under
> Windows, you might want to upgrade the type.)
>
> (I've looked at your code; I've no idea what the problem might be, but if
> you're porting from an int=32, long=64 implementation to an int=64, long=64
> one, I'm surprised you haven't got bigger differences. Certainly my own code
> would have a load of problems!)

The code's supposed to be portable, and not care as long as int>=32.
The one place it wanted strictly >32 I used long long (despite
obnoxious -Wall warnings about it). Anyway, I found the problem,
explained in subsequent followup, kind of along the lines you're
suggesting, but a rounding problem.

[Werner Wenzel]

Am 11.01.2014 01:06, schrieb Keith Thompson:
> N1570 6.5.7p3:

Please tell a non-native speaker what "p" in "6.5.7p3" stands for:

"point"? "phrase"?

Assuming that if refers to the number on the margin I would call it
"margin number", "marginal number", or "recital".

Thanks in advance.

[JohnF]

Stephen Sprunk <ste...@sprunk.org> wrote:
> On 10-Jan-14 07:21, JohnF wrote:
>> The code's supposed to be quite portable, and was originally
>> checked on intel linux, netbsd, freebsd, ms windows, and on
>> VAX and alpha OpenVMS. It always generated identical encrypted
>> files...until now.
>
> Are all of those systems ILP32, or is the Alpha one ILP64? (I've never
> used OpenVMS.) Have you tried it on Win64, which is IL32LLP64, or just
> Win32?
>
> Linux/x86-64 is I32LP64, so if that's the first such system you've
> ported to, that may indicate where the problem lies. If your code works
> on ILP64 systems, type problems seem unlikely, but you could still have
> int/long mismatches that wouldn't show up there--or on IL32LLP64.
>
> Also, you're using three different versions of GCC; it's possible that
> one of them has a bug (or "feature") that's triggered by some UB in your
> code and results in slight output changes. I'd highly suggest using the
> same version on all your systems, if possible, to eliminate that as a
> potential source of differences.
>
> Aside: Why roll your own encryption algorithm rather than use a proven,
> off-the-shelf algorithm, e.g. AES? Depending on OpenSSL's libcrypto is
> pretty standard these days; no sense reinventing the square wheel.
> S

Aw, c'mon Stephen, everybody rolls their own (oh, do you mean programs?:).
Though note that the program's forkosh.com/fm.html page (copy included
in forkosh.com/fm.zip distribution) says exactly what you're saying --
lots of existing stuff already does what it does. And fm.html provides
several links to lists of encryption utilities, i.e., a list of lists
of existing encryption programs. So, yeah, obviously, lots of stuff
already out there.

[JohnF]

Your #2 is wrong, as explicitly stated in the last parenthetical
"btw" sentence you quoted from me. Correct that, and it now can be.
In fact, it is.

[ais523]

"paragraph".

--
ais523

[luser- -droog]

I believe it stands for "paragraph".

[JohnF]

Eric Sosman <eso...@comcast-dot-net.invalid> wrote:
> On 1/10/2014 5:05 AM, JohnF wrote:
>> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
>> difference in the behavior of the exact same C code compiled
>> on one 64-bit linux machine...
>
> I concur with Ben Bacarisse's assessment of the code's
> readability; my head hurts, too!

Sorry about that, too (in addition to apology to Ben).
If either of you guys are ever in NYC, I'll buy you both
a few beers. And Eric gets an extra -- you pretty much
nailed the problem, which was more precisely a rounding
(actually, intentional truncating) difference when
I generated permutations (see below).

Well, go ahead and say it. Not only might it happen,
it pretty much does...

I first fixed up Ben's original guess about bitwise operations
on signed ints, but that was no help. So I turned off xor/xnor
operations for testing, but problem remained with just
bit-permutation encryption. So I turned off permutations,
leaving xor/xnor, and now problem disappeared.
And that was the beginning of the end for that bug.
I'd originally dismissed permutation problems,
thinking that would mess up entirely or not at all -- once
any random number changes, the seed gets changed, and then
the entire subsequent sequence changes. And that reasoning
was right, and random numbers were being generated identically.
But truncating to get an integer index from a floating 0.0-1.0
was behaving differently -- once in every 5000 cases
in test below.

Some new debugging output in permutation() func now displays
entire sequence of random ints used to generate a permutation.
In test case, it was called for n=29616, i.e., a random
permutation of 1,2,3,...,29616. It initializes p[i]=i+1 and
then generates random swaps in a loop, swapping p[i]<-->p[j]
where i=0...n-1 and,
int j = i + (int)(((float)(n-i))*ran1(stream,seed)); /*random i...n-1*/

I printf'ed all j's, redirected output to files, and diffed.
Diff output reproduced below: 6 numbers different out of 29616.
Top diff line is from 32-bit run, bottom line from 64.
It's got to be the intentional truncating in the above j=i+...
that's very occasionally behaving differently on 32- vs 64-bit,
when ran1() returns 0.999... Note that the int from the 32-bit
run always has a one-lower value.
And that's what's allowing the occasional permutation error,
without messing up the entire sequence. Never occurred to me.
So I paid very little attention to the permutation part of the code.
Thanks for all the help. Fyi, those diffs are...
271c271
< 15314 3090 5212 6467 9922 25042 15143 7413 25123 9071
---
> 15314 3090 5212 6467 9922 25042 15143 7414 25123 9071
322c322
< 20092 22664 21806 14761 4275 13431 8709 27394 19911 8583
---
> 20092 22664 21806 14761 4275 13431 8709 27395 19911 8583
449c449
< 17749 23068 27147 6689 25466 24802 7244 8462 7406 23700
---
> 17749 23068 27147 6689 25466 24802 7244 8462 7406 23701
1155c1155
< 25740 19807 16586 13952 25819 13810 27766 18252 15360 22940
---
> 25740 19807 16586 13952 25819 13810 27767 18252 15360 22940
1476c1476
< 21053 29163 28366 15367 21197 22616 17552 26731 20982 22816
---
> 21053 29163 28366 15367 21197 22616 17553 26731 20982 22816
1921c1921
< 22473 20864 29287 22011 19527 28185 22095 24022 22117 21598
---
> 22473 20865 29287 22011 19527 28185 22095 24022 22117 21598

[Jorgen Grahn]

On Fri, 2014-01-10, Ben Bacarisse wrote:
> JohnF <jo...@please.see.sig.for.email.com> writes:
> <snip>
>> The code is an en/de-cryption utility forkosh.com/fm.zip,
>> which is way too many lines to ask anybody to look at.
>
> Well, it's only about 1100 lines in one file, and about 740 that are not
> comment lines. Unfortunately it has inconsistent (and odd) spacing and
> indentation. It made my head hurt reading it!
>

> There are signs that it's not written by someone who knows C well --
> some odd idioms,

And a unique layout. I've not seen anything like it before. A FORTRAN
influence perhaps?

> unnecessary casts, not using prototype declarations,

That last one good way of making code break for 64-bit Linux. If the
compiler believes all function arguments are int, passing a long or
unsigned long will work on x86 because all involved types are 32 bits.
In contrast, on x86_64 int is 32 bits and a long is 64 bits.

> using signed types for bit operations... These things mean it's going
> to be harder work that one might hope. You'll need to decide if the
> pay-off is worth it.

Especially since free, standardized and widely used encryption
software is available.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[glen herrmannsfeldt]

JohnF <jo...@please.see.sig.for.email.com> wrote:
> Eric Sosman <eso...@comcast-dot-net.invalid> wrote:

(snip)

>> But I toughed it out with
>> Tylenol long enough to notice one possible source of trouble:
>> Your pseudo-random number generator produces `float' values.
>> Even if the internal mechanics of the generator are accurately
>> reproduced on all systems, the actual values used in subsequent
>> computations might not be. The C Standard gives implementations
>> some freedom in floating-point calculation, in particular:

>> "Except for assignment and cast (which remove all extra
>> range and precision), the values yielded by operators with
>> floating operands and values subject to the usual arithmetic
>> conversions and of floating constants are evaluated to a
>> format whose range and precision may be greater than
>> required by the type. [...]" -- 5.2.4.2.2p9

Pretty much never use floating point when you need exact
predictability. In the documentation for TeX, Knuth notes that
no floating point is used where it affects typesetting decisions
for similar reasons. One small change can effect line splitting
which affects page splitting, and pretty soon the result is
completely different. TeX does use floating point in some
messages that it prints out, though.

(snip)

> Well, go ahead and say it. Not only might it happen,
> it pretty much does...

(snip)

> And that was the beginning of the end for that bug.
> I'd originally dismissed permutation problems,
> thinking that would mess up entirely or not at all -- once
> any random number changes, the seed gets changed, and then
> the entire subsequent sequence changes. And that reasoning
> was right, and random numbers were being generated identically.
> But truncating to get an integer index from a floating 0.0-1.0
> was behaving differently -- once in every 5000 cases
> in test below.

It used to be that many random number generators were less random
in the low bits, and so the more obvious way of generating an
integer between 0 and N-1 was taking the generated value modulo N.

But this one looks like it shouldn't be so bad, and integer
modulo should be repeatable.

-- glen

[Jorgen Grahn]

On Sat, 2014-01-11, Jorgen Grahn wrote:
> On Fri, 2014-01-10, Ben Bacarisse wrote:

...

>> using signed types for bit operations... These things mean it's going
>> to be harder work that one might hope. You'll need to decide if the
>> pay-off is worth it.
>
> Especially since free, standardized and widely used encryption
> software is available.

I missed the fact that the OP is also the author of the software; I
somehow got the impression that he had downloaded it.

That certainly makes a difference -- I use my own programs instead of
standard ones, too.

[James Dow Allen]

One specific suggestion is to avoid all floating-point.
Use an integer-only PRNG.

James

[BartC]

"JohnF" <jo...@please.see.sig.for.email.com> wrote in message

news:laqtvd$2s2$1...@reader1.panix.com...

> Eric Sosman <eso...@comcast-dot-net.invalid> wrote:

>> So: The computations involving the `float' numbers you generate
>> might come out differently on different machines,

> But truncating to get an integer index from a floating 0.0-1.0
> was behaving differently -- once in every 5000 cases
> in test below.

How did you fix that?

--
Bartc

[Ben Bacarisse]

James Dow Allen <jdall...@yahoo.com> writes:

> One specific suggestion is to avoid all floating-point.
> Use an integer-only PRNG.

Yes and in fact that's what he's got. The floating point PRNG includes
an integer PRNG with final division step. I don't think the floating
point number are needed at all. I every case, the result of ran1 is
used to generate an integer. It would be very simple to switch to using
an integer-only PRNG.

--
Ben.

[Eric Sosman]

The RNG also governs whether the bytes are XOR'ed or XNOR'ed
with mask values, and how the eventual block of bits is permuted.
If encryption swaps bits X and Y while "the same" decryption
swaps X and (Y+1), there's a 25% chance of corruption. Sometimes
the corrupted byte will be in the discarded "noise," but sometimes
it will be payload.

--
Eric Sosman
eso...@comcast-dot-net.invalid

[James Dow Allen]

On Saturday, January 11, 2014 8:34:29 PM UTC+7, James Dow Allen wrote:
> One specific suggestion is to avoid all floating-point.

Oops. I now see this suggestion was already made.
Excuse me for skimming.

(My excuse was that after loading the code I figured
few would be masochistic enough to study it. :-)
I wasn't very masochistic myself, but the use of
'float' glared at me. Use of any floating-point
seems to me a no-no in general when results must
be reproduced across platforms.)

James

[Aleksandar Kuktin]

On Sat, 11 Jan 2014 06:56:44 +0000, JohnF wrote:

> Aleksandar Kuktin <aku...@gmail.com> wrote:
>> On Fri, 10 Jan 2014 10:05:47 +0000, JohnF wrote:
>>

>>> [snip]

>>>
>>> (By the way, the 32-vs-64-bit
>>> encrypted files are also ~one-in-a-thousand different, so both stages
>>> exhibit this small problem.)
>>

>> [snip]

>
> Your #2 is wrong, as explicitly stated in the last parenthetical "btw"
> sentence you quoted from me. Correct that, and it now can be.
> In fact, it is.

In my defense, the description confused me. (Which is why I asked.)

I'd post something about "well, that's your problem", and "turn off the
RNG to see if it will work that way" and so on, but you already solved
the problem so whatever...

[JohnF]

Aleksandar Kuktin <aku...@gmail.com> wrote:
> JohnF wrote:
>> Aleksandar Kuktin <aku...@gmail.com> wrote:
>>> JohnF wrote:
>>>> [snip]
>>>> (By the way, the 32-vs-64-bit
>>>> encrypted files are also ~one-in-a-thousand different, so both stages
>>>> exhibit this small problem.)
>>> [snip]
>>
>> Your #2 is wrong, as explicitly stated in the last parenthetical "btw"
>> sentence you quoted from me. Correct that, and it now can be.
>> In fact, it is.
>
> In my defense, the description confused me. (Which is why I asked.)

Sorry if followup sounded harsh. It wasn't meant to, but I was posting
several replies, maybe too quickly, and probably unintentionally
worded it poorly.

> I'd post something about "well, that's your problem", and "turn off the
> RNG to see if it will work that way" and so on, but you already solved
> the problem so whatever...

[JohnF]

I'm not sure I'm following that. So I'm equally unsure the following
remark is relevant: the rng ran1() was copied from Numerical Recipes
(as per attribution in comment block), but modified to generate several
independent streams. The xor/xnor and permute use two different
streams, for exactly the purpose of guaranteeing that decryption
reverses encryption. I'd think there's pretty much a 100% chance
things would immediately mess up otherwise. But a 0% chance (modulo
my bugs:) using the separate rng streams. Is that addressing what
you're saying?

[JohnF]

Excellent question. I wasn't sure exactly how when I posted,
but realized problem was eminently fixable, as follows.
As per forkosh.com/fm.html, with default max block size
and max noise bytes, biggest possible permutation is 67584 bits.
So I need to take an rng float (or double) 0.0-1.0, and use it to
choose between one of 67584 "bins". Since 1.0/67584.0 is well within
the "resolution"/precision of any conceivable float representation,
it's gotta be easily doable, one way or another.

The problem arises with current "formula" when the generated rn
gets near the "edge" of one of those "bins", and 32-bit apparently
truncates to lower-numbered bin, whereas 64-bit goes higher.
I say "apparently" because the first thing I tried was a little test,
as follows: changed the current little bin-choosing "formula"
int j = i + (int)(((float)(n-i))*ran1(stream,seed)); /*ran#i...n-1*/
to
int j = i + (int)(((double)(n-i))*((double)ran1(stream,seed)));

I expected that greater precision would maybe push the 32-bit
compiled executable "over the edge", so to speak, reproducing
the 64-bit numbers. It obviously couldn't change things the
other way round. Right??? ... Wrong. The 32-bit results remained
unchanged, and the 64-bit executable now chooses the lower
bin number wherever there used to be a diff/discrepancy.
How the heck that's happening, I don't know. You could say it
kind of solves the original problem, but since it's so weird
and unexpected, I have no faith it's a truly portable fix.
So I'll get around to a better, more robust, bin-choosing
formula. But since I now know -- thanks to you all -- exactly
where and what the problem is, and know that it's obviously
theoretically easily fixable, I'm not really worried about
it any longer.

[Aleksandar Kuktin]

On Sat, 11 Jan 2014 15:08:15 +0000, JohnF wrote:

> Sorry if followup sounded harsh. It wasn't meant to, but I was posting
> several replies, maybe too quickly, and probably unintentionally worded
> it poorly.

No problem about it. All is well in the land of C. :)

[JohnF]

Yeah, as per remarks in preceding followup explaining
"temporary fix/patch", I think the best permanent fix is probably what
you're saying (note: a preceding followup made the same "integer prng"
recommendation, but I'm not seeing who said it at the moment).
As mentioned in the rng's comment block, it's copied from
Numerical Recipes (with a little change to allow for several
concurrent but independent streams of random numbers).
And as most such rng's, output is float 0.0-1.0. I just left it
that way since that's what most rng's do anyway, and it was easy
enough to accommodate. Or so I thought. And so it appeared until now.

[Aleksandar Kuktin]

On Sat, 11 Jan 2014 15:49:13 +0000, JohnF wrote:

> So I need to take an rng float (or double) 0.0-1.0, and use it to choose
> between one of 67584 "bins". Since 1.0/67584.0 is well within the
> "resolution"/precision of any conceivable float representation, it's
> gotta be easily doable, one way or another.

Isn't C suppose to have a standard construct for rounding one way or the
other? I don't normally use floating point calculations if I don't
explicitly need to, but I think I remember reading in somefunc() man page
that you can request somefunc() to round this or that way.

[JohnF]

That kind of thought (if I recall) had crossed my
mind when copying ran1() from Numerical Recipes
back around y2k (to replace an even earlier rng
copied from the IBM Scientific Subroutine Package --
the guy who remarked that my coding style reminded
him of Fortran was right on:). But as pointed out
in preceding followup, I realized that distinguishing
between the max possible number of bins only required
1.0e-5 (or less) precision, and all 32-bit architectures
supplied some 100x better than that. What I failed
to think about was truncation behavior near bin edges:
the edges might look "fuzzier" to 32-bit executables.
But I guess using the rng's integer result should
get rid of that once and for all.

[osmium]

This thread says there sometimes is such a function. The key word to pursue
this question.is "banker's".

http://stackoverflow.com/questions/10845220/how-to-round-a-double-to-an-int-using-bankers-rounding-in-c

[Eric Sosman]

Not quite. I'm saying that even if ran1() returns the exact
same stream of `float' values on all machines (C does not guarantee
this, and "even as a practical matter" I'm not sure it will do so),
subsequent calculations involving those `float' values may produce
different results due to being carried out a different precisions
before rounding or truncating to produce a final integer answer.

My remark about "a 25% chance" was incorrect -- as I said,
the code seems unnecessarily obfuscated, and I hadn't the patience
to give it a really thorough reading. My thoughts about the swap
part went something like this:

- On machine A the program swaps the bits in positions X and Y,
while on machine B (due to different rounding) it swaps X
and Y+1. (Or X and Y-1, but that's the same case: Just
relabel A and B. Or X�1 and Y, but that's the same case:
Just relabel X and Y.)

- I'm assuming the off-by-one disagreements are rare, so the
likelihood of two disagreements in one swap is surpassingly
rare. It's conceivable that X�1 could swap with Y�1, but I
chose to ignore the possibility as negligible.

- If the bits at positions X, Y, and Y+1 all have the same value,
both swaps are no-ops and there's no corruption. This happens
25% of the time -- but that was my error: There's a 25% chance
of *no* damage, not a 25% chance damage will occur.

- Otherwise, the swaps will damage one, two, or three bytes
(where by "damage" I mean "come out differently on A and B").
Sometimes the damage will be to noise bytes, sometimes it
will be to payload. (In the "negligible" case of swapping
X�1 with Y�1 as many as four bytes could be damaged.)

- Subsequent "correct" swaps involving a damaged bit will not
increase the amount of damage, but will only move it around.

I don't see why you need multiple random streams -- it seems that
if you made the same sequence of calls on a single generator you'd
get the same results each time. But then, I haven't read the code
carefully.

--
Eric Sosman
eso...@comcast-dot-net.invalid

[JohnF]

Okay, got it.

> My remark about "a 25% chance" was incorrect

Yeah, that's what I was trying to figure. It sounded like
the result of some simple combinatoric/stochastic argument
that I just couldn't see.
(See bottom for answer to your other question.)

> -- as I said,
> the code seems unnecessarily obfuscated, and I hadn't the patience
> to give it a really thorough reading. My thoughts about the swap
> part went something like this:
>
> - On machine A the program swaps the bits in positions X and Y,
> while on machine B (due to different rounding) it swaps X
> and Y+1. (Or X and Y-1, but that's the same case: Just

> relabel A and B. Or X?1 and Y, but that's the same case:

> Just relabel X and Y.)
>
> - I'm assuming the off-by-one disagreements are rare, so the
> likelihood of two disagreements in one swap is surpassingly

> rare. It's conceivable that X?1 could swap with Y?1, but I

> chose to ignore the possibility as negligible.
>
> - If the bits at positions X, Y, and Y+1 all have the same value,
> both swaps are no-ops and there's no corruption. This happens
> 25% of the time -- but that was my error: There's a 25% chance
> of *no* damage, not a 25% chance damage will occur.
>
> - Otherwise, the swaps will damage one, two, or three bytes
> (where by "damage" I mean "come out differently on A and B").
> Sometimes the damage will be to noise bytes, sometimes it
> will be to payload. (In the "negligible" case of swapping

> X?1 with Y?1 as many as four bytes could be damaged.)

>
> - Subsequent "correct" swaps involving a damaged bit will not
> increase the amount of damage, but will only move it around.
>
> I don't see why you need multiple random streams -- it seems that
> if you made the same sequence of calls on a single generator you'd
> get the same results each time. But then, I haven't read the code
> carefully.

Should I leave the answer to that as a problem for the reader?
Code reading not really necessary to see the answer...
o On encryption it first xor/xnor's and then permutes.
o Therefore, on decryption [I bet you just figured it out:)]
it must first permute and then xor/xnor.
o If just one stream were used, the encryption xor/xnor random
numbers would be applied to the permute. What a mess.
o And for similar reasons, the generation of noise bytes
also requires its own separate rng stream.

[Aleksandar Kuktin]

Got it: ceil(), floor(), round(), rint() and others.

[Aleksandar Kuktin]

On Sat, 11 Jan 2014 15:49:13 +0000, JohnF wrote:

> As per forkosh.com/fm.html, with default max block size and max noise
> bytes, biggest possible permutation is 67584 bits.
> So I need to take an rng float (or double) 0.0-1.0, and use it to choose
> between one of 67584 "bins". Since 1.0/67584.0 is well within the
> "resolution"/precision of any conceivable float representation, it's
> gotta be easily doable, one way or another.

Out of curiosity - how did you come up with 67584? Its hexadecimal
representation - 0x10800 - isn't particularly round and I can't think of
any other magic properties that number could have.

I didn't read the code, if the answer is hiding in there.

[Ben Bacarisse]

JohnF <jo...@please.see.sig.for.email.com> writes:

> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>> James Dow Allen <jdall...@yahoo.com> writes:
>>
>>> One specific suggestion is to avoid all floating-point.
>>> Use an integer-only PRNG.
>>
>> Yes and in fact that's what he's got. The floating point PRNG includes
>> an integer PRNG with final division step. I don't think the floating
>> point number are needed at all. I every case, the result of ran1 is
>> used to generate an integer. It would be very simple to switch to using
>> an integer-only PRNG.
>
> Yeah, as per remarks in preceding followup explaining
> "temporary fix/patch", I think the best permanent fix is probably what
> you're saying (note: a preceding followup made the same "integer prng"
> recommendation, but I'm not seeing who said it at the moment).

Well there are some very good ones around (search for KISS and George
Marsaglia) but you don't need a new one. Your PRNG is an integer one,
it just does a final divide to return a float rather than an int. If it
is a good PRNG, the final int can be used instead of the divided float.
Unfortunately, for cryptographic work, you should have very strong
guarantees about the way it behaves, but since this PRNG is designed for
numerical work, you have probably tacitly assumed it is good enough.

To get some more confidence, test the integer PRNG suing any one of the
standard random test suites. It won't give you cryptographic levels of
confidence, but it will ensure that you can use all the bits with equal
confidence.

<snip>
--
Ben.

[Jorgen Grahn]

On Sat, 2014-01-11, JohnF wrote:
...
> The code's supposed to be portable, and not care as long as int>=32.
> The one place it wanted strictly >32 I used long long (despite
> obnoxious -Wall warnings about it).

-Wno-long-long is a decent cure for that. Or better, switch to C99
and tell the compiler you're doing it.

[BartC]

"JohnF" <jo...@please.see.sig.for.email.com> wrote in message

news:larp5p$7f9$1...@reader1.panix.com...

> BartC <b...@freeuk.com> wrote:

>> How did you fix that?
>
> Excellent question. I wasn't sure exactly how when I posted,
> but realized problem was eminently fixable, as follows.
> As per forkosh.com/fm.html, with default max block size
> and max noise bytes, biggest possible permutation is 67584 bits.
> So I need to take an rng float (or double) 0.0-1.0, and use it to
> choose between one of 67584 "bins". Since 1.0/67584.0 is well within
> the "resolution"/precision of any conceivable float representation,
> it's gotta be easily doable, one way or another.
>
> The problem arises with current "formula" when the generated rn
> gets near the "edge" of one of those "bins", and 32-bit apparently
> truncates to lower-numbered bin, whereas 64-bit goes higher.

If you're using ran1() to generate 0.0 to 1.0, couldn't differences start
from there? In that in one instance, the ran1() might return, say,
0.249999... and in another, 0.250000... from the same sets of integer start
values.

Looking at ran1(), it only seems to use floats to convert a 0 to 2147483647
integer result, to a 0.0 to 1.0 one. Could you make use of an integer random
function which returns the range 0 to 2147483647 as it is?

(If you integer-divide 0...2147483647 by 31775, you do get 0...67584 (just
about), which is close to the 0...67583 you seem to need. I don't know how
to get rid of that one out-of-range result without skewing the results.)

(BTW, there seems to be something 'off' about using a 23-bit float value
(1.0/2147483647) to multiply a 31-bit random integer. But probably OK unless
you try and recreate the 31-bit value from the result....)

--
Bartc

[glen herrmannsfeldt]

I think C is a little stricter, but there is a claim that a valid
Fortran floating point system could return 42.0 (or 42.D0) for all
floating point expressions.

Floating point is great for quantities that have a relative
uncertainty, and you want a value that is close to the right one.

This calculation is better done in fixed point.

The RNG already computes an integer between 0 and 21747483647,
the easy way is to take that modulo one more than the largest
value you want. The other way, when you have 64 bit arithmetic
available, is to multiply by the maximum+1 and divide by
2147483648 (the divide can be done as a shift).

Both will reliably and independent of any floating point
arithmetic give consistent values.

-- glen

[Eric Sosman]

On 1/11/2014 4:04 PM, glen herrmannsfeldt wrote:
> [...]

> This calculation is better done in fixed point.

A-men.

> The RNG already computes an integer between 0 and 21747483647,

Unlikely: The larger value requires >=35 bits, which isn't
usual these days. ;-) Also, isn't his RNG based on Park & Miller's
"Minimal Standard" generator? If so, the lower limit is not 0
but 1, and the upper is not 2147483647 but 2147483646.

> the easy way is to take that modulo one more than the largest
> value you want.

Many authors recommend against this, because the low-order
bits of maximum-period linear congruential generators have short
periods. But the "Minimal Standard" generator is not such a
generator: It's a pure congruential generator with prime modulus,
and its low-order bits are "as random as" the others.

> value you want. The other way, when you have 64 bit arithmetic
> available, is to multiply by the maximum+1 and divide by
> 2147483648 (the divide can be done as a shift).
>
> Both will reliably and independent of any floating point
> arithmetic give consistent values.

Yet another method is to use a rejection technique. If you
want a value in the range 0<=V<N and the generator produces values
in LO<=R<HI, you generate an R and compute V=(R-LO)/((HI-LO)/N).
If that's <N you're done; if not, throw it away, generate another R,
and keep trying. (In the worst case you'll reject a hair fewer
than half of the R's, so the average quantity of R's you need is
no worse than 1 + 1/2 + 1/4 + ... = 2.)

--
Eric Sosman
eso...@comcast-dot-net.invalid

[Keith Thompson]

JohnF <jo...@please.see.sig.for.email.com> writes:
[...]

> The code's supposed to be portable, and not care as long as int>=32.

Then it's only *mostly* portable; the standard allows int to be as
narrow as 16 bits. If you don't mind that restriction, that's fine (I'd
probably add a compile time assertion that int is at least 32 bits) --
or you might consider using int32_t and uint32_t when you need a 32-bit
type. Or [u]intleast32_t or [u]intfast32_t if you need *at least* 32
bits.

> The one place it wanted strictly >32 I used long long (despite

> obnoxious -Wall warnings about it). Anyway, I found the problem,
> explained in subsequent followup, kind of along the lines you're
> suggesting, but a rounding problem.

I'd probably use int64_t and friends. But what warnings do you get when
you use long long? You can likely get rid of any such warnings by
telling your compiler to conform to C99 or later.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[James Kuyper]

On 01/11/2014 04:04 PM, glen herrmannsfeldt wrote:
> Aleksandar Kuktin <aku...@gmail.com> wrote:
>> On Sat, 11 Jan 2014 15:49:13 +0000, JohnF wrote:

...

>> Isn't C suppose to have a standard construct for rounding one way or the

>> other? ...

In C99, several features were added that addressed rounding:
the macro FLT_ROUNDS was added to <float.h>; it expands to an expression
that will indicate the current rounding mode.

"A floating expression may be contracted, that is, evaluated as though
it were a single operation, thereby omitting rounding errors implied by
the source code and the expression evaluation method.89) The FP_CONTRACT
pragma in <math.h> provides a way to disallow contracted expressions."
(6.5p8)

fegetround() gets the current rounding direction, fesetround() sets it.
The possible rounding directions are identified by macros #defined in
<fenv.h>. They are all optional: #ifndef, the corresponding rounding
direction is not supported.

Several new functions were added to <math.h> for rounding to an integer
in various ways: nearbyint(), lrint(), round().


> ... I don't normally use floating point calculations if I don't

>> explicitly need to, but I think I remember reading in somefunc() man page
>> that you can request somefunc() to round this or that way.
>
> I think C is a little stricter, but there is a claim that a valid
> Fortran floating point system could return 42.0 (or 42.D0) for all
> floating point expressions.

C is a little stricter than that: Conversions to floating point type are
required to result in the nearest higher or nearest lower representable
value (6.3.1.4, 6.3.1.5), so (double)196 is not allowed to have a value
of 42.0. Also, "For decimal floating constants, and also for hexadecimal
floating constants when FLT_RADIX is not a power of 2, the result is
either the nearest representable value, or the larger or smaller
representable value immediately adjacent to the nearest representable
value, chosen in an implementation-defined manner.
For hexadecimal floating constants when FLT_RADIX is a power of 2, the
result is correctly rounded." (6.4.4.2p3), so the floating point
expression 3.0 is not allowed to have a value of 42.0. Also, all
floating point comparison operators (<, >, <=, >=, ==, !=) are required
to return either 0 or 1, and they must return the correct value - they
are not allowed to perform fuzzy comparisons.

However, unless an implementation of C chooses to pre-#define
__STDC_IEC_559__, in all other regards C is not very strict at all: "The
accuracy of the floating-point operations (+, -, *, /) and of the
library functions in <math.h> and <complex.h> that return floating-point
results is implementation defined, as is the accuracy of the conversion
between floating-point internal representations and string
representations performed by the library functions in <stdio.h>,
<stdlib.h>, and <wchar.h>. The implementation may state that the
accuracy is unknown."

Therefore, a conforming implementation of C is allowed to evaluate the
division in DBL_MIN/DBL_MAX < DBL_MAX with such lousy accuracy that the
comparison ends up being false.

If __STDC_IEC_559__ is pre-#defined, the implementation must conform to
the requirements of Annex K, which is based upon, but not identical
with, IEC 60559 (which in turn, is essentially equivalent to IEEE 754).
In that case, the floating point accuracy requirements are quite strict
- they come pretty close to being as strict as it is practically
possible for them to be. Which is still to low a requirement for this
kind of use.
--
James Kuyper

[JohnF]

Jorgen Grahn <grahn...@snipabacken.se> wrote:
> On Sat, 2014-01-11, JohnF wrote:
>> The code's supposed to be portable, and not care as long as int>=32.
>> The one place it wanted strictly >32 I used long long (despite
>> obnoxious -Wall warnings about it).
>
> -Wno-long-long is a decent cure for that. Or better, switch to C99
> and tell the compiler you're doing it. /Jorgen

It's no problem. I meant "obnoxious" humorously.
In fact, I'd rather continue seeing the warnings -- reminds me
I'm doing something a little funky that probably ought to be changed.

[JohnF]

Keith Thompson <ks...@mib.org> wrote:
> JohnF <jo...@please.see.sig.for.email.com> writes:
> [...]
>> The code's supposed to be portable, and not care as long as int>=32.
>

> Then it's only mostly portable; the standard allows int to be as
> narrow as 16 bits.

Yeah, but that's pretty much deprecated/archaic, at least for
general purpose computers. I usually just try to follow K&R 2nd ed
for "portable" syntax, whereas "portable semantics" gets trickier,
and I usually just try to figure "anything that can go wrong will".

> If you don't mind that restriction, that's fine (I'd
> probably add a compile time assertion that int is at least 32 bits) --
> or you might consider using int32_t and uint32_t when you need a 32-bit
> type. Or [u]intleast32_t or [u]intfast32_t if you need *at least* 32
> bits.
>
>> The one place it wanted strictly >32 I used long long (despite
>> obnoxious -Wall warnings about it). Anyway, I found the problem,
>> explained in subsequent followup, kind of along the lines you're
>> suggesting, but a rounding problem.
>
> I'd probably use int64_t and friends. But what warnings do you get when
> you use long long? You can likely get rid of any such warnings by
> telling your compiler to conform to C99 or later.

That might be preferable to LL. All three compilers
64-bit: cc --version cc (Debian 4.3.2-1.1) 4.3.2
32-bit: cc --version cc (NetBSD nb2 20110806) 4.5.3
cc --version cc (GCC) 4.7.1
issue similar -pedantic -Wall warnings. Explicitly, from 4.7.1,
fm.c: In function 'rseeder':
fm.c:865:6: warning: ISO C90 does not support 'long long' [-Wlong-long]
fm.c:866:11: warning: use of C99 long long integer constant [-Wlong-long]
fm.c:877:20: warning: ISO C90 does not support 'long long' [-Wlong-long]
fm.c:878:11: warning: ISO C90 does not support 'long long' [-Wlong-long]
fm.c:880:25: warning: use of C99 long long integer constant [-Wlong-long]
fm.c:880:30: warning: use of C99 long long integer constant [-Wlong-long]
fm.c:880:37: warning: use of C99 long long integer constant [-Wlong-long]
fm.c:892:3: warning: ISO C90 does not support the 'll' gnu_printf
length modifier [-Wformat]
But that whole function ought to be re-algorithmized anyway,
so my concern is pretty minimal.

[JohnF]

I think you're right that I mistakenly said "round" once or twice,
where I really should have said "truncate". Rounding isn't actually
an issue. The code is using a (random) float 0.0<=f<1.0 to calculate
an int ilo<=i<=ihi, with more-or-less the usual kind of formula
i = ilo + f*(ihi-ilo+1); better written as
i = ilo + (int)(f*(float)(ihi-ilo+1));
So I want it to truncate.

[JohnF]

Eric Sosman <eso...@comcast-dot-net.invalid> wrote:
> On 1/11/2014 4:04 PM, glen herrmannsfeldt wrote:
>> [...]
>> This calculation is better done in fixed point.

>> The RNG already computes an integer between 0 and 21747483647,
>
> Unlikely: The larger value requires >=35 bits, which isn't
> usual these days. ;-) Also, isn't his RNG based on Park & Miller's
> "Minimal Standard" generator? If so, the lower limit is not 0
> but 1, and the upper is not 2147483647 but 2147483646.

Yes, Park&Miller, according to the discussion in Numerical Recipes
in C, 2nd ed, page 280, from which I copied the code.

>> the easy way is to take that modulo one more than the largest
>> value you want.
>
> Many authors recommend against this, because the low-order
> bits of maximum-period linear congruential generators have short
> periods. But the "Minimal Standard" generator is not such a
> generator: It's a pure congruential generator with prime modulus,
> and its low-order bits are "as random as" the others.
>
>> value you want. The other way, when you have 64 bit arithmetic
>> available, is to multiply by the maximum+1 and divide by
>> 2147483648 (the divide can be done as a shift).
>>
>> Both will reliably and independent of any floating point
>> arithmetic give consistent values.
>
> Yet another method is to use a rejection technique. If you
> want a value in the range 0<=V<N and the generator produces values
> in LO<=R<HI, you generate an R and compute V=(R-LO)/((HI-LO)/N).
> If that's <N you're done; if not, throw it away, generate another R,
> and keep trying. (In the worst case you'll reject a hair fewer
> than half of the R's, so the average quantity of R's you need is
> no worse than 1 + 1/2 + 1/4 + ... = 2.)

Thanks, guys. I was just getting around to thinking about
the best way to handle this. Glad I read your discussion first.

[JohnF]

Answer's hiding in
http://www.forkosh.com/fm.html?algorithms.permutebits
(use the ?, not a #),
"With default block sizes randomly selected between
2048 and 8192 bytes, and with default noise between
32 and 256 bytes per block, fm's permutations range
between 16640 and 67584 bits."

[JohnF]

BartC <b...@freeuk.com> wrote:
> "JohnF" <jo...@please.see.sig.for.email.com> wrote in message
> news:larp5p$7f9$1...@reader1.panix.com...
>> BartC <b...@freeuk.com> wrote:
>
>>> How did you fix that?
>>
>> Excellent question. I wasn't sure exactly how when I posted,
>> but realized problem was eminently fixable, as follows.
>> As per forkosh.com/fm.html, with default max block size
>> and max noise bytes, biggest possible permutation is 67584 bits.
>> So I need to take an rng float (or double) 0.0-1.0, and use it to
>> choose between one of 67584 "bins". Since 1.0/67584.0 is well within
>> the "resolution"/precision of any conceivable float representation,
>> it's gotta be easily doable, one way or another.
>>
>> The problem arises with current "formula" when the generated rn
>> gets near the "edge" of one of those "bins", and 32-bit apparently
>> truncates to lower-numbered bin, whereas 64-bit goes higher.
>
> If you're using ran1() to generate 0.0 to 1.0, couldn't differences start
> from there? In that in one instance, the ran1() might return, say,
> 0.249999... and in another, 0.250000... from the same sets of integer start
> values.
>
> Looking at ran1(), it only seems to use floats to convert a 0 to 2147483647
> integer result, to a 0.0 to 1.0 one. Could you make use of an integer random
> function which returns the range 0 to 2147483647 as it is?

Yeah, that's been the suggestion, which I'll definitely be taking.

> (If you integer-divide 0...2147483647 by 31775, you do get 0...67584 (just
> about), which is close to the 0...67583 you seem to need. I don't know how
> to get rid of that one out-of-range result without skewing the results.)

Eric's preceding followup seems to contain the definitive discussion
about how to best do this.

> (BTW, there seems to be something 'off' about using a 23-bit float value
> (1.0/2147483647) to multiply a 31-bit random integer. But probably OK unless
> you try and recreate the 31-bit value from the result....)

Not sure myself. See Numerical Recipes in C, 2nd ed, page 280
for discussion of theory and algorithm.
I copied their code -- hopefully correctly.

[JohnF]

Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
> JohnF <jo...@please.see.sig.for.email.com> writes:
>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>> James Dow Allen <jdall...@yahoo.com> writes:
>>>
>>>> One specific suggestion is to avoid all floating-point.
>>>> Use an integer-only PRNG.
>>>
>>> Yes and in fact that's what he's got. The floating point PRNG includes
>>> an integer PRNG with final division step. I don't think the floating
>>> point number are needed at all. I every case, the result of ran1 is
>>> used to generate an integer. It would be very simple to switch to using
>>> an integer-only PRNG.
>>
>> Yeah, as per remarks in preceding followup explaining
>> "temporary fix/patch", I think the best permanent fix is probably what
>> you're saying (note: a preceding followup made the same "integer prng"
>> recommendation, but I'm not seeing who said it at the moment).
>
> Well there are some very good ones around (search for KISS and George
> Marsaglia) but you don't need a new one. Your PRNG is an integer one,
> it just does a final divide to return a float rather than an int.
> If it is a good PRNG, the final int can be used instead of the
> divided float.

Oh, yeah, that's what I understood you as saying, and what I intended
to do, from your previous remarks. Existing ran1() does what's needed.

> Unfortunately, for cryptographic work, you should have very strong
> guarantees about the way it behaves, but since this PRNG is designed for
> numerical work, you have probably tacitly assumed it is good enough.
>
> To get some more confidence, test the integer PRNG suing any one of the
> standard random test suites. It won't give you cryptographic levels of
> confidence, but it will ensure that you can use all the bits with equal
> confidence.

The section, starting on page 278 of Numerical Recipes in C, 2nd ed,
discusses (and provides code for) several rng's, including some tests.
Based on all that, you're right, I tacitly assumed ran1() okay.
Or okay enough. And, in any case, my fm.html page has a short
"Random number generation" <h3> section that ends up with
the "cya" remark,
"Of course, you're welcome to replace the "stock" versions of ran1( )
and rseeder( ) supplied in fm.zip with any other code of your own
choosing (keeping the same calling sequences, etc)."

[glen herrmannsfeldt]

JohnF <jo...@please.see.sig.for.email.com> wrote:
> Keith Thompson <ks...@mib.org> wrote:
(snip

>> Then it's only mostly portable; the standard allows int to be as
>> narrow as 16 bits.

> Yeah, but that's pretty much deprecated/archaic, at least for
> general purpose computers. I usually just try to follow K&R 2nd ed
> for "portable" syntax, whereas "portable semantics" gets trickier,
> and I usually just try to figure "anything that can go wrong will".

Well, pretty much int is the word size of the machine. On a PDP-11
or even 8 bit processors, int is usually 16 bits. Also, for the
early MS-DOS machines, before the 80386, and to later machines.

But VAX is a 16 bit word machine, but I would expect 32 bit int
for it, though I don't remember what VAX-C does.

The tradition from some years ago was to use short for 16 bits,
long for 32, but that got confusing when 64 bit systems came out.

-- glen

[Dr Nick]

Eric Sosman <eso...@comcast-dot-net.invalid> writes:

> On 1/11/2014 4:04 PM, glen herrmannsfeldt wrote:
>> [...]
>> This calculation is better done in fixed point.
>
> A-men.
>
>> The RNG already computes an integer between 0 and 21747483647,
>
> Unlikely: The larger value requires >=35 bits, which isn't
> usual these days. ;-) Also, isn't his RNG based on Park & Miller's
> "Minimal Standard" generator? If so, the lower limit is not 0
> but 1, and the upper is not 2147483647 but 2147483646.
>
>> the easy way is to take that modulo one more than the largest
>> value you want.
>
> Many authors recommend against this, because the low-order
> bits of maximum-period linear congruential generators have short
> periods. But the "Minimal Standard" generator is not such a
> generator: It's a pure congruential generator with prime modulus,
> and its low-order bits are "as random as" the others.

Another reason to do that is that it can lead to a bias in the numbers.

Consider a generator that produces 0-9 inclusive, with equal
probability. If you take the results mod 3 you get 3 instances of 1,
three of 2, and four of 0. It's a small bias, but a real one.

[glen herrmannsfeldt]

Dr Nick <nosp...@temporary-address.org.uk> wrote:
> Eric Sosman <eso...@comcast-dot-net.invalid> writes:

(snip, I wrote)

>>> the easy way is to take that modulo one more than the largest
>>> value you want.

>> Many authors recommend against this, because the low-order
>> bits of maximum-period linear congruential generators have short
>> periods. But the "Minimal Standard" generator is not such a
>> generator: It's a pure congruential generator with prime modulus,
>> and its low-order bits are "as random as" the others.

> Another reason to do that is that it can lead to a bias in the numbers.

> Consider a generator that produces 0-9 inclusive, with equal
> probability. If you take the results mod 3 you get 3 instances of 1,
> three of 2, and four of 0. It's a small bias, but a real one.

And, of course, using floating point there isn't any bias...

-- glen

[JohnF]

Dr Nick <nosp...@temporary-address.org.uk> wrote:
> Eric Sosman <eso...@comcast-dot-net.invalid> writes:
>> On 1/11/2014 4:04 PM, glen herrmannsfeldt wrote:
>>> [...]
>>> This calculation is better done in fixed point.

>>> The RNG already computes an integer between 0 and 21747483647,
>>
>> Unlikely: The larger value requires >=35 bits, which isn't
>> usual these days. ;-) Also, isn't his RNG based on Park & Miller's
>> "Minimal Standard" generator? If so, the lower limit is not 0
>> but 1, and the upper is not 2147483647 but 2147483646.
>>
>>> the easy way is to take that modulo one more than the largest
>>> value you want.
>>
>> Many authors recommend against this, because the low-order
>> bits of maximum-period linear congruential generators have short
>> periods. But the "Minimal Standard" generator is not such a
>> generator: It's a pure congruential generator with prime modulus,
>> and its low-order bits are "as random as" the others.
>
> Another reason to do that is that it can lead to a bias in the numbers.
> Consider a generator that produces 0-9 inclusive, with equal
> probability. If you take the results mod 3 you get 3 instances of 1,
> three of 2, and four of 0. It's a small bias, but a real one.

Fyi, the solution I've now coded was based on Eric's preceding (but
snipped here) discussion. His formula was a little opaque to me,
so I googled the keywords he introduced to come up with the following,
which is pseudocoded below from the real code in forkosh.com/fm.zip,
int iran1 ( int ilo, int ihi ) { /* you want int rn from ilo to ihi */
long ran1(/*some args go here*/), /*original rng from Numerical Recipes*/
iran = ran1(/*args*/), /* integer result from rng */
range = ihi-ilo+1, /* ihi-ilo+1 */
IM = 2147483647, /* ran1()'s actual range is 1...IM */
imax = IM - (IM%range); /* force iran's max to a multiple of range */
while ( iran >= imax ) iran=ran1(/*args*/); /*discard out-of-range iran*/
return ( ilo + (iran%range) ); } /* back with random ilo <= i <= ihi */

[Ike Naar]

On 2014-01-12, JohnF <jo...@please.see.sig.for.email.com> wrote:
> int iran1 ( int ilo, int ihi ) { /* you want int rn from ilo to ihi */
> long ran1(/*some args go here*/), /*original rng from Numerical Recipes*/
> iran = ran1(/*args*/), /* integer result from rng */
> range = ihi-ilo+1, /* ihi-ilo+1 */
> IM = 2147483647, /* ran1()'s actual range is 1...IM */

Isn't ran1()'s actual range [1..2147483646] ?

[J. Clarke]

In article <laoglr$cig$1...@reader1.panix.com>,
jo...@please.see.sig.for.email.com says...

>
> I'm getting a tiny-cum-microscopic, but nevertheless fatal,
> difference in the behavior of the exact same C code compiled
> on one 64-bit linux machine...

> o dreamhost.com
> uname -a Linux mothman 2.6.32.8-grsec-2.1.14-modsign-xeon-64 #2 SMP
> Sat Mar 13 00:42:43 PST 2010 x86_64 GNU/Linux

> cc --version cc (Debian 4.3.2-1.1) 4.3.2

> versus two other 32-bit linuxes...
> o panix.com
> uname -a NetBSD panix3.panix.com 6.1.2 NetBSD 6.1.2 (PANIX-USER) #0:
> Wed Oct 30 05:25:05 EDT 2013 i386

> cc --version cc (NetBSD nb2 20110806) 4.5.3

> o my own local box running slackware 14.0 32-bit

> cc --version cc (GCC) 4.7.1
>

> The code is an en/de-cryption utility forkosh.com/fm.zip,
> which is way too many lines to ask anybody to look at.
> But my own debugging is failing to identify where the
> difference creeps in, and googling failed to help suggest
> where to look more deeply.
>
> Firstly, both executables "work", i.e., if you encrypt and
> then decrypt, you get back the exact same original file.
> But if you encrypt using the 32-bit executable, scp the
> encrypted file to the 64-bit machine (md5's match) and then
> decrypt, the result is exactly the same length and almost
> identical except for about one byte in a thousand that doesn't
> diff. Vice versa (encrypt on 64-bit, decrypt on 32) gives
> the same behavior. (By the way, the 32-vs-64-bit encrypted files
> are also ~one-in-a-thousand different, so both stages exhibit
> this small problem.)
> And I tried cc -m32 on the 64-bit machine, but there's
> some stubs32.h that it's missing. So instead, I cc -static
> on my own box, and that executable does work on the 64-bit
> machine when run against files encrypted on either 32-bit box.
> So the problem doesn't seem to be the 64-bit os, but rather
> the cc executable, though I'm not 100% sure.
>
> What I'm really finding weird is that ~one-byte-in-a-thousand
> diff. The program uses several streams of random numbers
> (generated by its own code) to xor bytes, permute bits, etc.
> The slightest problem would garble up the data beyond belief.
> Moreover, it's got a verbose flag, and I can see the streams
> are identical. And everywhere else I've thought to look
> seems okay, too, as far as I can tell.
> So I'm asking about weird-ish 32/64-bit cc differences
> that might give rise to this kind of behavior. Presumably,
> there's some subtle bug that I'm failing to see in the code,
> and which the output isn't helping me to zero in on. Thanks,

I'm no expert but one thing I learned <mumble> years ago was to make
sure that the problem you're chasing really is the problem you _think_
you're chasing. You've got three different versions of the compiler
with two of them giving one behavior and the third, oldest one giving a
different behavior, which you are attributing to 64 bit vs 32-bit. It
could also be the result of some change made to the more recent releases
of the compiler and I would want to rule that out rather than assuming
that it's a 32- vs 64- bit issue.

[Keith Thompson]

JohnF <jo...@please.see.sig.for.email.com> writes:
> Keith Thompson <ks...@mib.org> wrote:
>> JohnF <jo...@please.see.sig.for.email.com> writes:
>> [...]
>>> The code's supposed to be portable, and not care as long as int>=32.
>>
>> Then it's only mostly portable; the standard allows int to be as
>> narrow as 16 bits.
>
> Yeah, but that's pretty much deprecated/archaic, at least for
> general purpose computers. I usually just try to follow K&R 2nd ed
> for "portable" syntax, whereas "portable semantics" gets trickier,
> and I usually just try to figure "anything that can go wrong will".

Most modern *hosted* implementations make int 32 bits, but there's
nothing deprecated or archaic about 16-bit int (at least as far as the C
standard is concerned).

POSIX requires at least 32 bits, so if your program already depends on
POSIX features, you can safely make that assumption. Otherwise, you can
certainly assume 32-bit or wider int if you want to, but I personally
would take care to make that assumption explicit, so if someone tries to
compile my code with a fully conforming implementation that happens to
have 16-bit int the problem will be detected early.

#include <limits.h>
#if INT_MAX < 2147483647
#error This code requires at least 32-bit int
#endif

[...]

>>> The one place it wanted strictly >32 I used long long (despite
>>> obnoxious -Wall warnings about it). Anyway, I found the problem,
>>> explained in subsequent followup, kind of along the lines you're
>>> suggesting, but a rounding problem.
>>
>> I'd probably use int64_t and friends. But what warnings do you get when
>> you use long long? You can likely get rid of any such warnings by
>> telling your compiler to conform to C99 or later.
>
> That might be preferable to LL. All three compilers
> 64-bit: cc --version cc (Debian 4.3.2-1.1) 4.3.2
> 32-bit: cc --version cc (NetBSD nb2 20110806) 4.5.3
> cc --version cc (GCC) 4.7.1
> issue similar -pedantic -Wall warnings. Explicitly, from 4.7.1,
> fm.c: In function 'rseeder':
> fm.c:865:6: warning: ISO C90 does not support 'long long' [-Wlong-long]
> fm.c:866:11: warning: use of C99 long long integer constant [-Wlong-long]
> fm.c:877:20: warning: ISO C90 does not support 'long long' [-Wlong-long]
> fm.c:878:11: warning: ISO C90 does not support 'long long' [-Wlong-long]
> fm.c:880:25: warning: use of C99 long long integer constant [-Wlong-long]
> fm.c:880:30: warning: use of C99 long long integer constant [-Wlong-long]
> fm.c:880:37: warning: use of C99 long long integer constant [-Wlong-long]
> fm.c:892:3: warning: ISO C90 does not support the 'll' gnu_printf
> length modifier [-Wformat]
> But that whole function ought to be re-algorithmized anyway,
> so my concern is pretty minimal.

Note how the warning is phrased: "ISO C90 does not support 'long long'".
The long long type has been a standard C feature since the 1999 standard
(and a common extension before that). Failure to support long long is
not merely deprecated, it's completely non-standard. If you're willing
to assume that int is at least 32 bits, you should be even more willing
to assume that long long exists.

And <stdint.h> also did not exist in C90; both it and long long were
introduced by C99.

Just invoke your compiler with options to tell it to use a more modern
version of the language.

gcc in particular uses "-std=gnu89" by default, which is C89/C90 with
GNU extensions. IMHO this is unfortunate, and it's time for gcc to
support C99 by default. But it probably doesn't make much sense to rely
on gcc's default anyway.

If you need your code to be portable to Microsoft's compiler, you might
have a problem; I don't remember whether it supports long long, but I
know it doesn't support C99 or C11.

[jacob navia]

Le 12/01/2014 22:09, Keith Thompson a �crit :

> #include <limits.h>
> #if INT_MAX < 2147483647
> #error This code requires at least 32-bit int
> #endif

A system with sizeof(int) of 16 bits will have problems with the above
constant "2147483647" since it is an integer constant that overflows
thompson

i would rather write

#if INT_MAX < 2147483647L

since long must be at least 32 bits


conclusion:
----------
if you want to be pedantic be padantic to the end thompson

[Kaz Kylheku]

On 2014-01-11, Jorgen Grahn <grahn...@snipabacken.se> wrote:
> On Sat, 2014-01-11, JohnF wrote:
> ...
>> The code's supposed to be portable, and not care as long as int>=32.
>> The one place it wanted strictly >32 I used long long (despite
>> obnoxious -Wall warnings about it).
>
> -Wno-long-long is a decent cure for that. Or better, switch to C99
> and tell the compiler you're doing it.

GCC's warnings about "long long" in C90 code (-ansi) are not a consequence of
-Wall. They are a consequence of -pedantic.

"long long" is a conforming extension to C90: it relies on grammar which
is a syntax error in C90, requiring a diagnostic.

The -pedantic mode means "generate all standard-required diagnostics" (or
rather, make an effort to do that, modulo bugs and omissions).

Try the following with "gcc -Wall -ansi". The only diagnostic you get is
about the unused variable:

#include <stdio.h>

long long x;

int main(void)
{
printf("hello, world\n");
int declaration_after_statement = 0;
return 0;
}

If you don't use -pedantic, you risk accidentally using extensions that you
don't intend to use. The cure for that is to compile your code base with
-pedantic once in a while and fix everything that you care to fix.


--
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1

[Ben Bacarisse]

jacob navia <ja...@spamsink.net> writes:

> Le 12/01/2014 22:09, Keith Thompson a écrit :
>> #include <limits.h>
>> #if INT_MAX < 2147483647
>> #error This code requires at least 32-bit int
>> #endif
>
> A system with sizeof(int) of 16 bits will have problems with the above
> constant "2147483647" since it is an integer constant that overflows
> thompson

No. What matters is the types intmax_t and uintmax_t and they can't be
anything like as small as 16 bits. See 6.10.1p4.

<snip>
--
Ben.

[Ben Bacarisse]

JohnF <jo...@please.see.sig.for.email.com> writes:

> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:

<snip>

>> Unfortunately, for cryptographic work, you should have very strong
>> guarantees about the way it behaves, but since this PRNG is designed for
>> numerical work, you have probably tacitly assumed it is good enough.
>>
>> To get some more confidence, test the integer PRNG suing any one of the
>> standard random test suites. It won't give you cryptographic levels of
>> confidence, but it will ensure that you can use all the bits with equal
>> confidence.
>
> The section, starting on page 278 of Numerical Recipes in C, 2nd ed,
> discusses (and provides code for) several rng's, including some tests.

They may be numerical tests based on the floating point value. It will
make almost no difference to a numerical test if the bottom bit of the
int (just before the final divide) cycles 0,1,1,0,1,1,0,... (for
example) but it will make a big difference if you make binary choices by
using ran1(...) & 1. Eric S suggests that this sort of thing does not
happen with the PRNG you use, but I'd not seen that post when I wrote.

> Based on all that, you're right, I tacitly assumed ran1() okay.

Assuming that the floats are well distributed, is not quite the same as
assuming that the ints have all the right properties so a test or two
would not go aims.

<snip>
--
Ben.

[Ike Naar]

On 2014-01-12, jacob navia <ja...@spamsink.net> wrote:
> Le 12/01/2014 22:09, Keith Thompson a ?crit :

1.6.10 p4:
"For the purposes of this token conversion and evaluation, all
signed integer types and all unsigned integer types act as if they
have the same representation as, respectively, the types intmax_t
and uintmax_t defined in the header <stdint.h>."

The maximum value of type intmax_t, INTMAX_MAX, is required to be
at least (2 to the power 63) - 1 (see 7.20.2.5 p1),
so 2147483647 <= INTMAX_MAX, and therefor "#if INT_MAX < 2147483647"
is valid even on implementations where INT_MAX < 2147483647,

[Ben Bacarisse]

When the floats are used to make an integer selection (i.e. you replace
int_rand() % max with floor(float_rand() * max)) the bias remains.

--
Ben.

[Keith Thompson]

And C90 had a similar rule, with preprocessor expressions evaluated in
type long or unsigned long. 2147483647 isn't a problem for any
conforming compiler. (And if you're using a non-conforming compiler,
you've got more problems than we can help you with here.)

[JohnF]

I wasn't really trying to make any big point. Nowadays I just think,
like you say wrt posix, it's reasonable not to worry about <32-bit
architectures, at least for general purpose programs not intended
to be embedded anywhere, etc. Portability across platforms has so
many pitfalls that you can't reasonably worry about every conceivable
one, but have to "choose your battles".
For example, one thing I dislike about mswin (in addition to what
you mention below) is that stdout isn't default binary mode, but
outputs two chars, crlf, for your one \n. Code that cares, and which
is intended to run on both win and unix, gets messy dealing with that.

Thanks for suggestions, but note above remark,
But that whole function [that uses long long] ought to be

re-algorithmized anyway, so my concern is pretty minimal.

And, as per a previous followup, the whole "obnoxious warnings"
remark was intended to be humorous, and I'd actually prefer
continuing to see the warnings, just to remind me that I should
get around to fixing the algorithm (it's the one that seeds
the rng with a hash-like number derived from your key -- I should
choose a better hash).

[JohnF]

Yes, actual max is IM-1, which code accommodates with >= in while().
I'll debug the comments later. But the whole bias problem solved by
all this is miniscule when range<<IM, which is pretty much always
the case. You can just comment out that while() and forget the whole
thing.

[John Forkosh]

Actually, I think your "amiss" went amiss :).
More to the point, I'm now using that iran1() function in preceding
followup, which (if you're not easily finding it) is,
"...the solution I've now coded was based on Eric's preceding
discussion.
It's pseudocoded below from the real code in forkosh.com/fm.zip,"
int iran1 ( int ilo, int ihi ) { /*you want an int rn from ilo to ihi*/

long ran1(/*some args go here*/), /*original rng from Numerical Recipes*/
iran = ran1(/*args*/), /* integer result from rng */

range = ihi-ilo+1, /* the range you want is ihi-ilo+1 */

IM = 2147483647, /* ran1()'s actual range is 1...IM */

imax = IM - (IM%range); /* force ran1's max to a multiple of range*/
while ( iran >= imax ) iran=ran1(/*args*/); /*reject out-of-range iran*/

return ( ilo + (iran%range) ); } /* back with random ilo <= i <= ihi */

So it's using mod arithmetic rather than &. But for the one instance
where a binary choice is needed, I do call iran1(0,1), meaning it
eventually does an iran%2, which is pretty much identical to iran&1.
Of course, I could instead do iran1(0,999)/500 to get 0 or 1.
That would be easy. Trying to come up with a valid test suite
would be harder than I care to contemplate. And if it reveals an
unwanted regularity in those ints, now what?...I have to go get
a whole different rng and start all over with it. Big pain.
But I will change that iran1(0,1). Thanks,

[JohnF]

J. Clarke <jclark...@cox.net> wrote:
> jo...@please.see.sig.for.email.com says...
>> <snip>

>> So I'm asking about weird-ish 32/64-bit cc differences
>> that might give rise to this kind of behavior. Presumably,
>> there's some subtle bug that I'm failing to see in the code,
>> and which the output isn't helping me to zero in on. Thanks,
>
> I'm no expert but one thing I learned <mumble> years ago was to make
> sure that the problem you're chasing really is the problem you _think_
> you're chasing. You've got three different versions of the compiler
> with two of them giving one behavior and the third, oldest one giving a
> different behavior, which you are attributing to 64 bit vs 32-bit. It
> could also be the result of some change made to the more recent releases
> of the compiler and I would want to rule that out rather than assuming
> that it's a 32- vs 64- bit issue.

Problem found and fixed, as per earlier followups.
Turned out to be slightly different float behavior.
But you could be right that it wasn't a 64-bit issue,
per se. And I'd tried cc -m32-bit, as per previous
followups, but compiler barfed at that switch (not
sure why, man cc wasn't on that box). So I couldn't
try to get a finer-grained understanding of problem.

[Ike Naar]

There's still a bias:
The result from ran1() is in the range [1..2147483646]
Take, for example, [ilo..ihi] = [0..1],
then range = 2 and imax = 2147483646
After discarding out-of-range values of iran, we
end up with iran in the range [1..imax-1] = [1..2147483645].

There are 1073741822 numbers in that range that are 0 (mod 2),
the lowest number being 2, the highest number being 2147483644.
There are 1073741823 numbers in that range that are 1 (mod 2),
the lowest number being 1, the highest number being 2147483645.
So the outcome 0 has a smaller probability than the outcome 1.

[JohnF]

Ah, yes. Shh, don't breathe a word to anybody,
but right now, as we speak, I'm submitting my patent
application for my new algorithm that takes an
integer odd number of items, and separates them
into two equal-sized piles.
Can you say "internet billionaire"?

[Keith Thompson]

JohnF <jo...@please.see.sig.for.email.com> writes:
[...]

> For example, one thing I dislike about mswin (in addition to what
> you mention below) is that stdout isn't default binary mode, but
> outputs two chars, crlf, for your one \n. Code that cares, and which
> is intended to run on both win and unix, gets messy dealing with that.

[...]

stdout is a text stream in *all* C implementations.

The difference is in the way Windows and, say, UNIX represent
text files. In UNIX, the end of a line is indicated by a single
linefeed ('\n') character; in Windows, it's marked by a carriage
return followed by a linefeed ('\r', '\n').

For text streams, C translates a single newline character to the local
system's end-of-line representation on output, and vice versa on input.

The point of this is to make it *easier* to write portable code that
deals with text files. For example, you can write a single line to
stdout like this:

printf("Hello, world\n");

rather than:

if (running_on_windows) {
printf("Hello, world\r\n"); /* unnecessary */
}
else {
printf("Hello, world\n");
}

Things do become a bit more difficult if you have to deal with "foreign"
text files, but that's pretty much unavoidable.

And if you want to read and write binary files, just use a binary
stream; stdout isn't intended to deal with binary files.

[JohnF]

Keith Thompson <ks...@mib.org> wrote:
> JohnF <jo...@please.see.sig.for.email.com> writes:
> [...]
>> For example, one thing I dislike about mswin (in addition to what
>> you mention below) is that stdout isn't default binary mode, but
>> outputs two chars, crlf, for your one \n. Code that cares, and which
>> is intended to run on both win and unix, gets messy dealing with that.
> [...]
>

> stdout is a text stream in all C implementations.

> For text streams, C translates a single newline character to the local
> system's end-of-line representation on output, and vice versa on input.

> And if you want to read and write binary files, just use a binary
> stream; stdout isn't intended to deal with binary files.

Thanks for the info. Here's the problem that I've encountered.
Lots of my programs are cgi's that emit binary files, typically
gifs, used in html as, e.g.,
<img src="/cgi-bin/myprog.cgi?instructions and/or data for image">
In this case, myprog >>has to<<, as I understand it, emit to stdout.
Is that right? If so, I need to put stdout in "binary mode"
(that's what windows calls it, the typical win C command being
something like setmode(fileno(stdout),O_BINARY)).
Got a fix for, or insight into, dealing with that without
messy #ifdef stuff? Thanks,

[JohnF]

Sorry for following myself up:
I should have mentioned that several "intended-to-be-portable"
fixes that I've tried, in particular freopen("CON","wb",stdout)
and stdout=fdopen(STDOUT_FILENO,"wb"), don't work or don't work
portably, for one reason or another (tales of woe elided:)
So I'm asking for a pretty much known-to-portably-work fix.

[James Kuyper]

On 01/14/2014 03:19 AM, JohnF wrote:
> JohnF <jo...@please.see.sig.for.email.com> wrote:
...

>> Lots of my programs are cgi's that emit binary files, typically
>> gifs, used in html as, e.g.,
>> <img src="/cgi-bin/myprog.cgi?instructions and/or data for image">
>> In this case, myprog >>has to<<, as I understand it, emit to stdout.
>> Is that right? If so, I need to put stdout in "binary mode"
>> (that's what windows calls it, the typical win C command being
>> something like setmode(fileno(stdout),O_BINARY)).
>> Got a fix for, or insight into, dealing with that without
>> messy #ifdef stuff? Thanks,
>
> Sorry for following myself up:
> I should have mentioned that several "intended-to-be-portable"
> fixes that I've tried, in particular freopen("CON","wb",stdout)
> and stdout=fdopen(STDOUT_FILENO,"wb"), don't work or don't work
> portably, for one reason or another (tales of woe elided:)

For freopen(), "It is implementation-defined which changes of mode are
permitted (if any), and under what circumstances.", so you can't count
on that to work.

fdopen() is a POSIX function; I've no idea whether the function with
that name that you're trying to use on a mswin system is supposed to
conform fully to POSIX specifications for that function. More
importantly, stdout is only required to be an expression of the type
"pointer to FILE"; it's not required to be the name of a pointer
variable that you can assign to. For instance, an implementation of
<stdio.h> could have:

extern FILE __std_streams[];
#define stdout (&__std_streams[0])
#define stdin (&__std_streams[1])
#define stderr (&_std_streams[2])

You could get around that problem, at least, by assigning the value
returned by fdopen() in your own pointer, rather than trying to store it
in stdout.

> So I'm asking for a pretty much known-to-portably-work fix.

I can't help you with that. The last time I did any CGI work was more
than a decade ago, and the output was pure text, so the fact that stdout
is in text mode wasn't a problem. Also, it was on a unix-like system
where there's no difference between text mode and binary mode.
--
James Kuyper

[Stephen Sprunk]

On 13-Jan-14 00:31, JohnF wrote:
> Problem found and fixed, as per earlier followups. Turned out to be
> slightly different float behavior. But you could be right that it
> wasn't a 64-bit issue, per se. And I'd tried cc -m32-bit, as per
> previous followups, but compiler barfed at that switch

Shouldn't that be "-m32"?

http://gcc.gnu.org/onlinedocs/gcc-4.7.3/gcc/i386-and-x86_002d64-Options.html#i386-and-x86_002d64-Options

> (not sure why, man cc wasn't on that box). So I couldn't try to get a
> finer-grained understanding of problem.

Just Google "man gcc"; that's available nearly everywhere.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

[Keith Thompson]

I really don't know.

stdout is *intended* for text output. On Unix-like systems, you
happen to be able to write binary data to a text stream without
any problems (because the end-of-line translation doesn't need to
do anything), but C in general doesn't guarantee that will work.

Normally, you'd write binary data by opening a file (not stdout)
in binary mode and writing to it.

If CGI imposes a requirement to write binary data to stdout,
then I'm sure there's a solution; I just have no idea what
it is. Try Googling and/or posting in another forum. There's a
comp.infosystems.www.authoring.cgi newsgroup, but I have no idea
whether it's still active. I've found stackoverflow.com to be a
good site for this kind of question. But first check for existing
answers; you're unlikely to be the first person to run into this.