25 October 2010, 18:14 | #161 | ||
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Quote:
The problem here is that bad multiplication constants can still produce reasonable looking results. There's actually quite some math theory behind those multiply constants, so I'd be careful with them if I were you. This is also the reason why I'm simply using existing generators that use multiplies, and also use the constants they advise. Much safer than experimenting. This in turn leads to my whole logical operator based PRNG experiments. I simply thought they were easier to get right, but as it turns out, PRNGs aren't easy to get right without proper math theory. So it's not about insisting, but more about showing why I find multiplies hard to get right (although in the beginning I avoided them for speed reasons ). Quote:
As for it's usage: The idea is to extract a small table of, say, 1024 bytes (initial zero state doesn't matter much now), and use those values for seeding or generating random values. For seeding it's probably a good idea to pre-process the data first. Edit: Here's an interesting page (text!) about hash functions and block ciphers: http://burtleburtle.net/bob/hash/index.html Last edited by Thorham; 26 October 2010 at 20:19. |
||
26 October 2010, 17:54 | #162 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
I accidentally posted the wrong version of my entropy extractor (test version) It basically writes out which bits changed rather than the actual bits that changed. Big difference. Here's the right routine:
Code:
;------------------------------------------------------------------------------ ;Test code. ;------------------------------------------------------------------------------ start lea out,a0 move.l #1024*64,d0 bsr.w rng.extract_entropy rts ; ; extract_entropy ; ; Extracts entropy from the Amigas hardware state. The extraction is bit ; difference based: The routine starts with a hardware state buffer filled ; with zeros. The routine then reads the hardware registers, reads the state, ; writes the registers to the state and then XORs the registers with the state. ; Each byte that isn't zero is now written to a table. ; ; The state is always overwritten completely. There is no state mixing. This ; means the difference between the current state and the previous state is the ; data you get, and only those values that changed. ; ; The idea behind this is that because there is a lot of redundant information in ; the hardware state, that it's better to use only the bits that change from state ; read to state read, while discarding what doesn't change. ; ;in d0=seed size in long words. ; rng.extract_entropy movem.l d0-a6,-(sp) move.l d0,d6 lea out,a3 moveq #0,d0 moveq #0,d1 .loop lea regs_cia,a0 lea regs_chip,a1 lea dif,a4 moveq #5,d7 .loopr move.l (a0)+,a2 move.b (a2),d0 move.l (a1)+,a2 move.w (a2),d1 move.l d1,d2 lsr.l #8,d2 move.b (a4),d3 move.b d0,(a4)+ move.b (a4),d4 move.b d1,(a4)+ move.b (a4),d5 move.b d2,(a4)+ eor.b d0,d3 beq.b .l1 and.b d3,d0 move.b d0,(a3)+ subq.l #1,d6 .l1 eor.b d1,d4 beq.b .l2 and.b d4,d1 move.b d1,(a3)+ subq.l #1,d6 .l2 eor.b d2,d5 beq.b .l3 and.b d5,d2 move.b d2,(a3)+ subq.l #1,d6 .l3 tst.l d6 blt.b .exit .next_regs dbra d7,.loopr .next bra.b .loop .exit movem.l (sp)+,d0-a6 rts regs_cia dc.l $bfd800,$bfd900,$bfe601,$bfe701,$bfe801,$bfec01 regs_chip dc.l $dff000,$dff004,$dff006,$dff008,$dff00e,$dff014 ;------------------------------------------------------------------------------ ;Used by the test code. ;------------------------------------------------------------------------------ section data,data_f dif dcb.l 1024 out dcb.l 1024*1024 leftover dcb.b 1024 ;------------------------------------------------------------------------------ |
27 October 2010, 05:27 | #163 |
2 contact me: email only!
Join Date: May 2001
Location: Auckland / New Zealand
Posts: 3,187
|
You could always go to random.org, grab a few hundred/thousand values, choose a starting position, read a bunch of those out in a loop and every so often reset the position to somewhere else in the table!
|
27 October 2010, 20:01 | #164 | |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Quote:
Extracting entropy available on the machine is both easy and effective, and a whole randomness oriented library is also not difficult to write, pretty short, and very effective, too, especially when combined with entropy extraction |
|
28 October 2010, 09:21 | #165 | ||
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,323
|
Quote:
Quote:
|
||
28 October 2010, 18:24 | #166 | ||
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Quote:
Quote:
The reason is simply that the Amiga's hardware state isn't exactly rich in entropy, and you can't get every possible value if you extract the exact number of bytes that your PRNG's seed is long each time. In my opinion, this process of extracting more entropy and mixing it up into a smaller size is a necessity. |
||
29 October 2010, 20:25 | #167 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Here's the improved version of my state extractor. It now only writes out the state bits that have changed. The previous routine outputted the changed bits on a per byte basis. The problem with that was that there was still quite some redundant information in the data, and what's worse is that the spectral test showed a lot of correlation.
When outputting only the bits that changed, the 2D spectral correlation has gone away, and a simple plot looks amazingly random. This routine is much better than the previous one, but it's also a lot slower. However, with this routine you don't have to extract a lot of data to be able to generate good seeds. Note that this one still starts with an empty previous state table. It was more important to get the code to work properly. Now that it does, I'll change this Check it out: Code:
;------------------------------------------------------------------------------ ;Test code. ;------------------------------------------------------------------------------ start lea out,a0 move.l #1024,d0 bsr.w rng.extract_entropy rts ; ; extract_entropy ; ; Extracts entropy from the Amiga's hardware state. Only those bits that have ; changed since the previous state read are written out. ; ; The idea behind this is that because there is a lot of redundant information in ; the hardware state, that it's better to use only the bits that change from state ; read to state read, while discarding what doesn't change. ; ;in d0=seed size in long words. ; rng.extract_entropy movem.l d0-a6,-(sp) move.l d0,a6 lea out,a3 moveq #32,d6 .loop lea regs,a0 lea dif,a4 moveq #6*3-1,d7 .loop_regs move.l (a0)+,a2 move.b (a2),d0 move.b (a4),d1 move.b d0,(a4)+ eor.b d0,d1 moveq #1,d3 moveq #7,d5 .loop_bits move.b d1,d2 and.b d3,d2 beq .l1 move.b d0,d2 and.b d3,d2 add.l d4,d4 or.b d2,d4 subq.l #1,d6 bne .l1 move.l d4,(a3)+ moveq #32,d6 subq.l #1,a6 tst.l a6 beq .exit .l1 add.l d3,d3 .next_bits dbra d5,.loop_bits .next_regs dbra d7,.loop_regs .next bra .loop .exit movem.l (sp)+,d0-a6 rts regs dc.l $bfd800,$bfd900,$bfe601,$bfe701,$bfe801,$bfec01 dc.l $dff000,$dff004,$dff006,$dff008,$dff00e,$dff014 dc.l $dff001,$dff005,$dff007,$dff009,$dff00f,$dff015 ;------------------------------------------------------------------------------ ;Used by the test code. ;------------------------------------------------------------------------------ section data,data_f dif dcb.l 1024 out dcb.l 1024*1024 leftover dcb.b 1024 ;------------------------------------------------------------------------------ Last edited by Thorham; 30 October 2010 at 15:07. |
01 November 2010, 08:38 | #168 | ||
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,323
|
Quote:
Quote:
And DFF004/DFF008 don't seem to be exactly random either. |
||
01 November 2010, 17:59 | #169 | |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Quote:
However, DFF000 and DFF008 seem to be fine values to me. If they're not, explain why please. Anyway, what do you think? Good? Bad? Tell me And suggestions are welcome, too. Also, do you have anything new? Edit: Here's a nice page about cryptography, which has a whole book in downloadable chapters (PDF): http://www.cacr.math.uwaterloo.ca/hac/ Might be interesting Edit2: Checked DFF000.w and DFF008.w and they're interesting, but problematic and don't seem to add much. I could be wrong, but after removing them from the register table, the distribution of the random bits improved. It's now about 88 out of 256. Should be 128 out of 256, of course, but it's certainly better. Sadly I still have to extract four times the seed length, and then XOR the four tables (so to speak) into one Last edited by Thorham; 02 November 2010 at 23:47. |
|
03 November 2010, 16:21 | #170 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Okay, here's the corrected version of my seeder. What I did wrong was based on premature optimization As Donald Knuth puts it: 'Premature optimization is the root of all evil'.
I was shifting the AND mask in D3 to the left for each iteration in the bits loop (.loop_bits) and than ORing the data into the accumulation register D4. Wrong Now it simply gets bit 0 and shifts the difference reg and the data reg instead. Man, what a dumb mistake Anyway, the advantage is that the distribution is now about 50/50, and that no bit mixing of any kind is needed anymore. Hurray If you spot any more silly mistakes let me know Code:
;------------------------------------------------------------------------------ ;Test code. ;------------------------------------------------------------------------------ start lea out,a0 bsr rng.init_state move.l #1024*8,d0 bsr.w rng.extract_entropy rts ; ; rng.init state ; ; Initializes the state table. ; rng.init_state movem.l d0-a6,-(sp) lea regs,a0 lea dif,a4 moveq #11-1,d7 .loop move.l (a0)+,a2 move.b (a2),d0 move.b d0,(a4)+ .next dbra d7,.loop movem.l (sp)+,d0-a6 rts ; ; rng.extract_entropy ; ; Extracts entropy from the Amigas hardware state. The routine writes out the ; bits that changed from state read to state read. ; ;in d0=seed size in long words. ; rng.extract_entropy movem.l d0-a6,-(sp) move.l d0,a6 lea out,a3 moveq #32,d6 .loop lea regs,a0 lea dif,a4 moveq #1,d3 moveq #11-1,d7 .loop_regs move.l (a0)+,a2 move.b (a2),d0 move.b (a4),d1 move.b d0,(a4)+ eor.b d0,d1 beq .next_regs moveq #7,d5 .loop_bits move.b d1,d2 and.b d3,d2 beq .l1 move.b d0,d2 and.b d3,d2 add.l d4,d4 or.b d2,d4 subq.l #1,d6 bne .l1 move.l d4,(a3)+ moveq #32,d6 subq.l #1,a6 tst.l a6 beq .exit .l1 lsr.l #1,d0 lsr.l #1,d1 .next_bits dbra d5,.loop_bits .next_regs dbra d7,.loop_regs .next bra .loop .exit movem.l (sp)+,d0-a6 rts regs dc.l $bfd800,$bfd900,$dff006 dc.l $bfe601,$dff014,$bfe701,$dff005 dc.l $bfe801,$dff007,$bfec01,$dff00f ;------------------------------------------------------------------------------ ;Used by the test code. ;------------------------------------------------------------------------------ section data,data_f counter dc.l 0 dif dcb.l 1024 out dcb.l 1024*1024 leftover dcb.b 1024 ;------------------------------------------------------------------------------ |
04 November 2010, 12:10 | #171 | |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,323
|
Quote:
I'm not actually deep in that subject, so i have nothing else to say. |
|
05 November 2010, 18:17 | #172 | ||
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Quote:
As for the last value on the bus: I assume this is the chipmem bus? Wouldn't such a value be difficult, or perhaps even impossible to predict? Especially if you run an extractor that only uses those two registers from chipmem instead of fastmem (make sure the program cache gets invalidated, or it possibly won't have any effect)? Quote:
Anyway, I've considered your idea of using user input as a source of entropy. I think it would be best to setup an interrupt handler of some sort that monitors the user's input, collects the data and sends it out to the seeder/rng as more entropy (or collects it in pools that a seeder/rng can use). Is it difficult/annoying to setup a system friendly interrupt handler? |
||
07 November 2010, 09:03 | #173 | |||
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,323
|
Quote:
Anyway, i've read several values from DFF008, displayed them and here they are : Code:
FFFF FFFF FFFF 0000 0003 0000 FFFF FFFF FFFF FFFF 0000 0000 FFFF FFFF FFFF Quote:
Quote:
Anyway, if you want to monitor that stuff, you'd better add a handler to input.device rather than setting up an interrupt (which is quite easy but it's another story). |
|||
07 November 2010, 18:53 | #174 | ||
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Quote:
The experiments I've done do show randomness in simple 2D plots, but there's a lot of redundant information associated with these registers, and I have a hard time removing it. I could use software whitening, but this is slow. The whitening option does work, though. The reason it's slow is because of the sheer amount of data that is thrown away, which means it takes much longer to fill up a buffer of a given size. Anyway, those registers would be nice to add, but aren't mandatory. Quote:
1) Mouse pointer location. 2) Mouse button clicks. 3) Time between mouse movements. 4) Time between mouse button clicks. 5) Raw keyboard code. 6) Time between key presses. Much of this is wasted when just reading the registers directly. You'd only get small timing changes, and this is very little entropy. Using a handler is definitely better. Yes, that does sound like a much better idea |
||
11 November 2010, 09:32 | #175 | |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,323
|
Quote:
|
|
11 November 2010, 20:59 | #176 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
I don't know if I'm going to do it, but giving a programmer who uses this library the option to easily set this up would be nice, and fits perfectly in a full blown RNG library. This is also the reason why I'm not limiting my library to just one or two algorithms
|
15 November 2010, 08:27 | #177 | |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,323
|
Quote:
But i am not sure a full blown library has any advantage over a single, simple to use, function... |
|
15 November 2010, 17:55 | #178 | |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Quote:
While your generator might be nice, it does only one thing, and this will not be enough for some |
|
18 November 2010, 09:08 | #179 | |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,323
|
Quote:
If anyone wants the very same sequence, they have an internal RNG whose properties are known. If you intend to support all cases in a library, your library will become HUGE. Is that what you want ? You can have a look at TestU01's rng library to see what this means. Is that really what you want ? |
|
18 November 2010, 18:47 | #180 | |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 47
Posts: 3,770
|
Quote:
For Amiga purposes this is quite a good setup, and it doesn't result in thousands of lines of code, and is therefore not too big at all. All routines except the hardware state based generator are already written, and just need testing, and it wasn't much work at all |
|
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Random question | 251Mario | project.EAB | 1 | 16 May 2013 02:19 |
HELP! A600 number 2 down! :( | Snowy | support.Other | 5 | 04 December 2011 22:12 |
Help needed!!Random octal numbers generator(asm) | sheryn88 | Coders. General | 6 | 01 August 2010 07:19 |
Random crashes | ami_stuff | support.WinUAE | 8 | 06 February 2009 16:51 |
D/Generation | IanMac | support.Games | 2 | 04 November 2002 16:47 |
|
|