On Wed, Mar 24, 2010 at 05:06:33PM +0100, Joachim Breitner wrote: > Given that I take the code directly from the xscreensaver distribution, > I’d be surprised if the bug would be in yarandom.c. If it is so, it > should probably be fixed there.
Yes, I supposed that was the case. I'll check the source code, and if necessary, file a bug there. > I’m excited what you’ll find out! Okay. I've basically made ya_rand_init print out the initial seed, and the value of the seed variable for each iteration of the loop[0]. It looks like the randomization doesn't get very far; that is, it seems to stop after item 6 or 7. This means that the rest of the array a doesn't ever change. Since the initial indices into the array (i1 and i2) are dependent on a[0], the place in the sequence where the characters repeat is different, but the characters end up the same. Note that eventually, the array would be completely different, but this probably take several hundred iterations of ya_random in order to fully randomize the array. My solution here is to take a hint from several cryptographic algorithms: the bitwise rotate. Since the multiplications will have a larger effect on the upper bits than the lower bits, after every addition in the seeding algorithm, we perform a bitwise rotate by an odd number. Therefore, we get a better distribution of randomness throughout the bits. The performance impact should be negligible: the seed algorithm is used only upon startup and on many architectures, a bitwise rotate will reduce to one instruction. Testcases are included as dump7, dump8, and dump9. Notice the difference in results: all of the seeds are different. A patch to fix the problem (without any of the debugging code) is included as unicode-screensaver.patch. [0] Patch attached with all my debugging code as testcase-patch, and output is dump4, dump5, and dump6. -- brian m. carlson / brian with sandals: Houston, Texas, US +1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187
seed: 1498778444 1269447104 305180 30896 seed 0: 1498778444 seed 1: 3347577750 seed 2: 3553678345 seed 3: 3572913453 seed 4: 3449180658 seed 5: 26340386 seed 6: 4238395159 seed 7: 3139844920 seed 8: 1765455632 seed 9: 249894102 seed 10: 2862650822 seed 11: 1934424947 seed 12: 3946334426 seed 13: 893882962 seed 14: 282418914 seed 15: 3337456293 seed 16: 4063640600 seed 17: 1456266001 seed 18: 2084338244 seed 19: 2013417811 seed 20: 1672727686 seed 21: 3277832919 seed 22: 238399337 seed 23: 2223835908 seed 24: 4278758797 seed 25: 2823113278 seed 26: 2032757340 seed 27: 4047024539 seed 28: 691675622 seed 29: 2491878712 seed 30: 3485108586 seed 31: 4205646929 seed 32: 4177548273 seed 33: 116056487 seed 34: 1521740894 seed 35: 811200388 seed 36: 3700549221 seed 37: 26460693 seed 38: 3821452569 seed 39: 4024399421 seed 40: 662524303 seed 41: 1440649427 seed 42: 1101389507 seed 43: 50185664 seed 44: 301797180 seed 45: 1160484976 seed 46: 1693314400 seed 47: 286320951 seed 48: 3925834299 seed 49: 2769977430 seed 50: 1741736614 seed 51: 1553344048 seed 52: 4189437349 seed 53: 1865897184 seed 54: 867788524 2 17d87bd2 0 2dfe1d12 0000145c 000852 001d23 2 01ba4926 0 109922f1 0000145c 001241 00a710 2 1cdba6c3 1 70d295ae 00000c00 0009ae 002128 2 d469965e 0 d70d397a 0000145c 000b02 00205e 2 6d80071d 1 7e048751 00000c00 000751 001e50 2 c8583abb 1 d792c813 00000c00 000013 000033 2 a7a31772 0 8d8bfa95 0000145c 000779 001503 2 0e42d8d1 1 2fd9f9f8 00000c00 0009f8 002192 2 0fab837c 0 0fdea953 0000145c 000303 00035a 2 b6957ebc 0 a3262606 0000145c 00010e 00014f 2 ba87e7f5 1 799b6eae 00000c00 0002ae 000311
seed: 2035890869 1269447720 841101 30936 seed 0: 2035890869 seed 1: 3830603750 seed 2: 3238036745 seed 3: 3649905965 seed 4: 2815382002 seed 5: 3739348002 seed 6: 4255172375 seed 7: 2334538552 seed 8: 1765455632 seed 9: 249894102 seed 10: 2862650822 seed 11: 1934424947 seed 12: 3946334426 seed 13: 893882962 seed 14: 282418914 seed 15: 3337456293 seed 16: 4063640600 seed 17: 1456266001 seed 18: 2084338244 seed 19: 2013417811 seed 20: 1672727686 seed 21: 3277832919 seed 22: 238399337 seed 23: 2223835908 seed 24: 4278758797 seed 25: 2823113278 seed 26: 2032757340 seed 27: 4047024539 seed 28: 691675622 seed 29: 2491878712 seed 30: 3485108586 seed 31: 4205646929 seed 32: 4177548273 seed 33: 116056487 seed 34: 1521740894 seed 35: 811200388 seed 36: 3700549221 seed 37: 26460693 seed 38: 3821452569 seed 39: 4024399421 seed 40: 662524303 seed 41: 1440649427 seed 42: 1101389507 seed 43: 50185664 seed 44: 301797180 seed 45: 1160484976 seed 46: 1693314400 seed 47: 286320951 seed 48: 3925834299 seed 49: 2769977430 seed 50: 1741736614 seed 51: 1553344048 seed 52: 4189437349 seed 53: 1865897184 seed 54: 867788524 2 64c9b4e5 1 28b082d7 00000c00 000ad7 00252c 2 dcf9c503 1 857b1321 00000c00 000b21 00258d 2 28753f85 1 284727a3 00000c00 0003a3 00043f 2 770ecf95 1 16e22bc6 00000c00 0003c6 000470 2 7f3be75a 0 15efc306 0000145c 0012d6 00fb73 2 7f4d2c8f 1 254a0ae0 00000c00 000ae0 002535 2 4ca54ad8 0 c99566b0 0000145c 000834 001d04 2 8ac15d6f 1 9fce57ec 00000c00 000bec 010909 2 efc01b0b 1 8696e116 00000c00 000516 000740 2 6ad7b20b 1 a06e586f 00000c00 00046f 000550 2 6d0a1af2 0 65b0571d 0000145c 00042d 00049c
seed: 1210184716 1269447867 16062 30947 seed 0: 1210184716 seed 1: 1685739414 seed 2: 4181693449 seed 3: 1177703725 seed 4: 1918259698 seed 5: 496102434 seed 6: 3164653335 seed 7: 3139844920 seed 8: 1765455632 seed 9: 249894102 seed 10: 2862650822 seed 11: 1934424947 seed 12: 3946334426 seed 13: 893882962 seed 14: 282418914 seed 15: 3337456293 seed 16: 4063640600 seed 17: 1456266001 seed 18: 2084338244 seed 19: 2013417811 seed 20: 1672727686 seed 21: 3277832919 seed 22: 238399337 seed 23: 2223835908 seed 24: 4278758797 seed 25: 2823113278 seed 26: 2032757340 seed 27: 4047024539 seed 28: 691675622 seed 29: 2491878712 seed 30: 3485108586 seed 31: 4205646929 seed 32: 4177548273 seed 33: 116056487 seed 34: 1521740894 seed 35: 811200388 seed 36: 3700549221 seed 37: 26460693 seed 38: 3821452569 seed 39: 4024399421 seed 40: 662524303 seed 41: 1440649427 seed 42: 1101389507 seed 43: 50185664 seed 44: 301797180 seed 45: 1160484976 seed 46: 1693314400 seed 47: 286320951 seed 48: 3925834299 seed 49: 2769977430 seed 50: 1741736614 seed 51: 1553344048 seed 52: 4189437349 seed 53: 1865897184 seed 54: 867788524 2 0fdea953 1 b6957ebc 00000c00 000abc 002511 2 a3262606 0 ba87e7f5 0000145c 0006a1 001425 2 799b6eae 0 9cb06173 0000145c 0009af 001eec 2 08cc787e 0 d0f57e32 0000145c 0007ca 00155e 2 33926e3c 0 a8d87a87 0000145c 0003b3 000422 2 1538d403 1 f2204321 00000c00 000b21 00258d 2 f2fc3f85 1 66f727a3 00000c00 0007a3 001ea6 2 360ecf95 1 46e22bc6 00000c00 0003c6 000470 2 7f3be75a 0 15efc306 0000145c 0012d6 00fb73 2 7f4d2c8f 1 254a0ae0 00000c00 000ae0 002535 2 4ca54ad8 0 c99566b0 0000145c 000834 001d04
Only in unicode-screensaver-0.2/debian: patches
Only in unicode-screensaver-0.2: .pc
diff -ur unicode-screensaver.old/unicode.c unicode-screensaver-0.2/unicode.c
--- unicode-screensaver.old/unicode.c 2010-03-23 21:18:56.000000000 +0000
+++ unicode-screensaver-0.2/unicode.c 2010-03-24 16:10:55.000000000 +0000
@@ -11,6 +11,7 @@
*
*/
+#include <stdio.h>
#include <X11/Xft/Xft.h>
#include "unicode-names.h"
@@ -125,12 +126,15 @@
struct unicode_state *state = (struct unicode_state *)void_state;
if (state->blank) {
+ unsigned int rand1, rand2;
XWindowAttributes xgwa;
XGetWindowAttributes (dpy, win, &xgwa);
- font = random() % NUM_FONTS;
+ rand1 = random();
+ font = rand1 % NUM_FONTS;
- pickn = random() % state->font_count[font];
+ rand2 = random();
+ pickn = rand2 % state->font_count[font];
pickc = 0;
for (ucs4 = FcCharSetFirstPage (state->fonts[font]->charset,
map, &next);
@@ -145,7 +149,8 @@
if (pickc++ == pickn)
pick = ucs4 + i * 32 + j;
}
-
+ fprintf(stderr, "%d %08x %d %08x %08x %06x %06x\n", NUM_FONTS,
rand1,
+ font, rand2, state->font_count[font], pickn,
pick);
sprintf(name,"U+%04X: ",pick);
strcat(name, get_unicode_data_name(pick));
diff -ur unicode-screensaver.old/utils/yarandom.c
unicode-screensaver-0.2/utils/yarandom.c
--- unicode-screensaver.old/utils/yarandom.c 2010-03-23 21:18:56.000000000
+0000
+++ unicode-screensaver-0.2/utils/yarandom.c 2010-03-24 16:10:55.000000000
+0000
@@ -55,6 +55,7 @@
# include "config.h"
#endif
+#include <stdio.h>
#ifdef HAVE_UNISTD_H
# include <unistd.h> /* for getpid() */
#endif
@@ -111,12 +112,16 @@
#endif
/* ignore overflow */
seed = (999*tp.tv_sec) + (1001*tp.tv_usec) + (1003 * getpid());
+ fprintf(stderr, "seed: %u %ld %ld %d\n", seed, tp.tv_sec, tp.tv_usec,
+ getpid());
}
a[0] += seed;
+ fprintf(stderr, "seed %2d: %u\n", 0, seed);
for (i = 1; i < VectorSize; i++)
{
seed = a[i-1]*1001 + seed*999;
+ fprintf(stderr, "seed %2d: %u\n", i, seed);
a[i] += seed;
}
--- unicode-screensaver.old/utils/yarandom.c 2010-03-23 21:18:56.000000000 +0000
+++ unicode-screensaver-0.2/utils/yarandom.c 2010-03-24 16:55:43.000000000 +0000
@@ -86,6 +86,12 @@
static int i1, i2;
+static inline unsigned int
+rotl32(unsigned int x, int n)
+{
+ return (x << n) | (x >> (32 - n));
+}
+
unsigned int
ya_random (void)
{
@@ -110,13 +116,21 @@
gettimeofday(&tp);
#endif
/* ignore overflow */
- seed = (999*tp.tv_sec) + (1001*tp.tv_usec) + (1003 * getpid());
+ seed = (999 * tp.tv_sec);
+ seed = rotl32(seed, 11);
+ seed += (1001 * tp.tv_usec);
+ seed = rotl32(seed, 7);
+ seed += (1003 * getpid());
+ seed = rotl32(seed, 13);
}
a[0] += seed;
for (i = 1; i < VectorSize; i++)
{
- seed = a[i-1]*1001 + seed*999;
+ seed = seed*999;
+ seed = rotl32(seed, 9);
+ seed += a[i-1]*1001;
+ seed = rotl32(seed, 15);
a[i] += seed;
}
seed: 2863388317 1269449205 809815 827 seed 0: 2863388317 seed 1: 2648845583 seed 2: 1225115968 seed 3: 2651085543 seed 4: 2608034509 seed 5: 3391839692 seed 6: 4110473501 seed 7: 269277426 seed 8: 2357930748 seed 9: 1644975338 seed 10: 286160624 seed 11: 2299560263 seed 12: 3160666662 seed 13: 1796087328 seed 14: 3849670015 seed 15: 3199926076 seed 16: 2929559504 seed 17: 1717118852 seed 18: 1622257768 seed 19: 3400721038 seed 20: 1252672928 seed 21: 1974065905 seed 22: 3274881280 seed 23: 76861739 seed 24: 228125123 seed 25: 2971953129 seed 26: 424399638 seed 27: 3970369613 seed 28: 2172996891 seed 29: 3101993008 seed 30: 3293675439 seed 31: 3470157639 seed 32: 3372668827 seed 33: 4017001323 seed 34: 1172391118 seed 35: 2416147396 seed 36: 2906797506 seed 37: 241730200 seed 38: 3068807591 seed 39: 3259111956 seed 40: 3534311640 seed 41: 674267114 seed 42: 1929087337 seed 43: 2661577615 seed 44: 130367785 seed 45: 768823423 seed 46: 4216272621 seed 47: 4087888598 seed 48: 3766331120 seed 49: 972357811 seed 50: 2021894557 seed 51: 1097076480 seed 52: 117416190 seed 53: 1355711924 seed 54: 4214591806 2 74eeff1d 1 14430263 00000c00 000263 0002c6 2 b80cfcd0 0 6c633b5a 0000145c 000736 0014bd 2 b977a1f3 1 f524246b 00000c00 00086b 001f82 2 4809041b 1 2dfd1610 00000c00 000210 000273 2 8ebeb862 0 8ca15a3e 0000145c 00034a 0003b9 2 e427688c 0 03d1c8a1 0000145c 000e79 0025f3 2 38ce7cdc 0 25445290 0000145c 000bf0 0021b6 2 4f09d554 0 525f1001 0000145c 001415 01d5a1 2 3f513444 0 a7797bd5 0000145c 000f49 002711 2 60e2254e 0 e3d5f2cc 0000145c 0013b0 01d320 2 36613cb2 0 acca44b5 0000145c 0006e5 00146c
seed: 4104218718 1269449292 583552 837 seed 0: 4104218718 seed 1: 995332467 seed 2: 1257052211 seed 3: 3162978487 seed 4: 4104931646 seed 5: 21240383 seed 6: 685217887 seed 7: 2329982629 seed 8: 38868057 seed 9: 183887875 seed 10: 3063296158 seed 11: 263505592 seed 12: 1983592780 seed 13: 1326451240 seed 14: 316445525 seed 15: 3788227882 seed 16: 1749224063 seed 17: 1324481683 seed 18: 1966200482 seed 19: 3709307973 seed 20: 985140663 seed 21: 3882317236 seed 22: 3393945376 seed 23: 1037491777 seed 24: 2089557110 seed 25: 3574652218 seed 26: 2371341488 seed 27: 1612129471 seed 28: 4242603211 seed 29: 2229215113 seed 30: 1758474906 seed 31: 2821844271 seed 32: 1833890455 seed 33: 355607474 seed 34: 3926835626 seed 35: 2949576945 seed 36: 2177889427 seed 37: 897234265 seed 38: 414625995 seed 39: 3821597873 seed 40: 3866172441 seed 41: 2952091185 seed 42: 1906055661 seed 43: 1146804333 seed 44: 2390196191 seed 45: 55032499 seed 46: 2314359672 seed 47: 2919767326 seed 48: 3180213101 seed 49: 2953005001 seed 50: 1303916526 seed 51: 4055948374 seed 52: 333255608 seed 53: 4087863130 seed 54: 3871244477 2 dada8075 1 b49daf91 00000c00 000b91 00fffd 2 7da497f8 0 8a7e926b 0000145c 001287 00fb1d 2 7d950d49 1 1d104133 00000c00 000533 000913 2 8d96bb6c 0 f400530a 0000145c 000322 000390 2 752d9a38 0 f7cffbf7 0000145c 00033f 0003ae 2 f4c7403e 0 efe763ee 0000145c 00102e 00282b 2 d62c9421 1 4b8c9ae5 00000c00 0006e5 0010dc 2 0c3bc317 1 d0f460bd 00000c00 0008bd 001fd8 2 e5598cc5 1 f1a8114f 00000c00 00094f 00207d 2 19054df7 1 5fd84f29 00000c00 000329 00039e 2 4ae4b425 1 dfb0f889 00000c00 000889 001fa0
seed: 757052036 1269449476 385705 844 seed 0: 757052036 seed 1: 2081675189 seed 2: 883163720 seed 3: 1436480076 seed 4: 3135647061 seed 5: 818384771 seed 6: 1202977662 seed 7: 1315574611 seed 8: 3062720273 seed 9: 3423153854 seed 10: 1000465362 seed 11: 3608087655 seed 12: 2614116151 seed 13: 1839861274 seed 14: 669576407 seed 15: 781688090 seed 16: 2779424432 seed 17: 1667062823 seed 18: 1589298313 seed 19: 1821178075 seed 20: 1607385479 seed 21: 608866376 seed 22: 3443475929 seed 23: 839675991 seed 24: 1921817670 seed 25: 1731511289 seed 26: 2265783636 seed 27: 2217469291 seed 28: 3774055229 seed 29: 1019531368 seed 30: 3983347808 seed 31: 3897382734 seed 32: 1612006223 seed 33: 3981553000 seed 34: 3754220984 seed 35: 721879798 seed 36: 2624424636 seed 37: 1199551339 seed 38: 272197382 seed 39: 1728180447 seed 40: 1886619930 seed 41: 3019448142 seed 42: 1299822884 seed 43: 2891975558 seed 44: 2210637936 seed 45: 687898726 seed 46: 2459672244 seed 47: 1755492529 seed 48: 3886333061 seed 49: 1605173717 seed 50: 1571681351 seed 51: 2701730188 seed 52: 502483609 seed 53: 1172881393 seed 54: 3807485001 2 14efd620 0 27beafbf 0000145c 000263 0002a4 2 1ca82140 0 be48c48e 0000145c 000542 000607 2 51019dda 0 78a74fbe 0000145c 001266 00a749 2 87bba6bf 1 9de03a85 00000c00 000a85 0022e2 2 06306fb1 1 2786ea04 00000c00 000204 000267 2 37040e03 1 869dd19a 00000c00 00059a 000994 2 36392e5a 0 3a086f5b 0000145c 000e4f 0025c9 2 070df552 0 0698adce 0000145c 000b32 0020a2 2 43b111fd 1 1c0a1479 00000c00 000479 00055c 2 6e690916 0 94dff635 0000145c 0001cd 00020e 2 a69f86fb 1 73be7bac 00000c00 000bac 01039a
signature.asc
Description: Digital signature
