Re: [hackers] Re: [sbase] Orphan patches and unsent patches
On Sun, Mar 03, 2024 at 03:05:47PM +0100, Eolien55 wrote: > but should we not rather implement "Debiased Int Mult (t-opt)"? Both should be fine. The integer mul method avoids clz() so that could be a reason to prefer it. > arc4random(3) doesn't uses seeds, which means that I cannot initialize > it wrong. I see, that makes sense. You had the right idea on one of your eariler patch about mixing malloc-ed address and time but the implementation wasn't good. srandom((intptr_t)buf.nlines | time(NULL)); OR isn't a good mixer because it's biased towards 1 (it's also not reversible): 0 | 0 = 0 0 | 1 = 1 1 | 0 = 1 1 | 1 = 1 XOR would be better. But even better would be to hash it before xor-ing. Just a multiply by an large-ish odd number is usually sufficient: seed = ((uintptr_t)malloced_addr * 0xAC5533CD) ^ time(NULL) /* or use nanoseconds */; You could also mix in a stack address and/or the address of a (usually) dynamically linked function the same way. This should be enough to get a decent seed without relying on system specific interfaces. (See also: https://nullprogram.com/blog/2019/04/30/) - NRK
Re: [hackers] Re: [sbase] Orphan patches and unsent patches
NRK wrote: > I'd recommend using the bitmask approach described in here: > https://www.pcg-random.org/posts/bounded-rands.html#bitmask-with-rejection-unbiased-apples-method I thought the approach used by OpenBSD was simpler, and performed better, becaused it avoided the loop, which might cause the algorithm to repeat itself, overall slowing the algorithm. It seems not to be the case according to this link. However, the 2 last approaches described (Debiased Int Mult, (t-opt) and (t-opt, m-opt)) seem to perform better, for small-constant benchmarks, small-shuffle and all-ranges-shuffle, with non-negligible performance gains. Where Bitmask performs better, the difference seems negligible. I see that the implementation I sent doesn't have good performance, but should we not rather implement "Debiased Int Mult (t-opt)"? > And if you want a portable clz without depending on __builtin_clz() then see: > https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 I'll work on that, thanks. > I'm not sure why you think arc4random() is better. I doubt you need any > cryptograhic guarantees here. rand(3) could not be used because RAND_MAX causes some problems. random(3) needs a seed, and a good random seed is tricky to get. We can't read from /dev/urandom because it might be that we're in a chroot ; the timestamp can be quite random on its lower bits, but it changes too slowly. Nanoseconds seem okay, but I'm not sure whether or not it's sufficiently random. arc4random(3) doesn't uses seeds, which means that I cannot initialize it wrong (ie., use a PRNG in a way that its results aren't random). > Personally I'd just go with a simple PCG construction. It takes about > ~6 lines of code [0], is fast and has good statistical properties. > Would also avoid spending time locking/unlocking mutex inside libc for > no reason. I think it's a good idea to have our own fast PRNG, but I originally thought it was better to trust the implementers of libc for making a _random_ PRNG. I will play with the PRNG you've sent me though. Thank you -- Elie Le Vaillant
Re: [hackers] Re: [sbase] Orphan patches and unsent patches
On Sun, Mar 03, 2024 at 12:58:20AM +0100, Elie Le Vaillant wrote: > I'm using the web interface to the mailing list to check what has been > sent, and these patches were not sent. The web archive is not reliable and often drops mails. > + * Copied off OpenBSD (original is arc4random_uniform) > + */ > +uint32_t > +random_uniform(uint32_t upper_bound) I'd recommend using the bitmask approach described in here: https://www.pcg-random.org/posts/bounded-rands.html#bitmask-with-rejection-unbiased-apples-method And if you want a portable clz without depending on __builtin_clz() then see: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 > + r = random(); /* arc4random() is better, but we don't always > have it */ I'm not sure why you think arc4random() is better. I doubt you need any cryptograhic guarantees here. Personally I'd just go with a simple PCG construction. It takes about ~6 lines of code [0], is fast and has good statistical properties. Would also avoid spending time locking/unlocking mutex inside libc for no reason. [0]: https://github.com/imneme/pcg-c-basic/blob/bc39cd76ac3d541e618606bcc6e1e5ba5e5e6aa3/pcg_basic.c#L60-L67 or: https://codeberg.org/NRK/slashtmp/src/branch/master/prng/pcg_32.c - NRK
