Shop OBEX P1 Docs P2 Docs Learn Events
Random/LFSR on P2 - Page 24 — Parallax Forums

Random/LFSR on P2

1212224262792

Comments

  • TorTor Posts: 2,010
    edited 2017-09-19 16:24
    Yep. I expect that there will be plenty of solutions that work as easily as the QS board does. I just have a hard time understanding why rigging up a keyboard and a monitor would be considered simpler than just plugging straight into a notebook.. I just don't get it. I've done that exercise (connecting stuff to a kbd and a monitor) so many times over the years, and it is and has always been a mess and an inconvenience.
  • Lol, I'm gonna 3D print mine. Will be portable, or bench, the necessary items integrated, similar to a notebook. I've got some models, components, just kind of queued.

    For prototyping, obviously board, display, etc...

    On my bench, the necessary stuff is out there. Plug in, go. Honestly, I will probably leave it there most times, like any other bit of bench gear.

    I do like, and will use serial / USB regularly. It's like you say, quick.

  • Heater.Heater. Posts: 21,230
    That is one annoying feature of the Raspberry Pi. You can't just plug it into a USB port and talk to it.
  • Right? I keep a couple P1 boards handy for that plug in, test case. It's super easy.
  • TonyB_TonyB_ Posts: 2,178
    edited 2017-09-19 23:58
    jmg wrote: »
    TonyB_ wrote: »
    The drawback with RCZR & RCZL is they are sequential. Imagine if any register could hold 16 copies of the flags, with random access for both reading and writing in a single instruction. All flag worries would disappear. Something for the P3 perhaps?
    It comes down to the Logic cost - to me that's looking a LOT of Bit-Muxes needed, vs a simpler shifter for the RCZR
    evanh wrote: »
    The existing generic barrel shifter in the ALU should be able to handle it if we wanted to throw a full two-operand opcode at the job.

    Thanks for the feedback.

    Although 16 flag sets is the maximum possible with 32-bit D and 9-bit S, eight sets should be enough in practice. D[1:0] = CZ[0], D[3:2] = CZ[1], etc., leaving D[31:16] unused if the limit is eight in the logic. However, the top 16 bits could be switched in as a second bank of eight by simply rotating the words.

    The proposed XCZ instruction has a couple of interesting and possibly unique properties:

    1. The letters in the mnemonic are adjacent on the same keyboard row. Any other instructions like that?

    2. The D,S form might never by used, as only the very brave or mad would use a register to specify the flag addresses. Any other instructions like that?

    :)
  • jmgjmg Posts: 15,173
    TonyB_ wrote: »
    2. The D,S form might never by used, as only the very brave or mad would use a register to specify the flag addresses. Any other instructions like that?

    I'm rusty on the details, but I think Chip already has bit-index instructions, so this becomes a dual-bit (doublit?) variant on that ?

  • Heater. wrote: »
    That is one annoying feature of the Raspberry Pi. You can't just plug it into a USB port and talk to it.

    exactly!

    With the current boot loader you are able to do that, but need to type in some monitor in hex.

    Since auto baud works on every space, you just need to type steady. Or be able to copy and paste into the terminal.

    But it would be nicer to have some minimalistic monitor. Hot-P2 one is maybe to much, but I really liked it. Like Chip said, just add access to the smart pins and ready.

    Some small documented hooks to get in between the serial communication to extend the cmd-interface of the debugger, and we are golden.

    Mike



  • TonyB_TonyB_ Posts: 2,178
    edited 2017-09-21 23:20
    Could a kind soul please post the first 10 XORO32 sums when seed = 1?
  • evanhevanh Posts: 15,915
    edited 2017-09-22 12:32
    Here's a hack up of old testing code (ie: Not the actual Prop2's XORO32):
    evanh@control:~/hoard/rng_testing$ gcc -o seq20-xo "src/xoroshiro128plus-seq20.c" -O3
    evanh@control:~/hoard/rng_testing$ ./seq20-xo
    0001 4085 5530 2c7c 769f a248 dffd 202d f2f1 5aca 4dc8 d1d1 adcd 0598 1b30 8094 540c d6a4 9c9d 2eac

    EDIT: And the source code:
    #include <limits.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <stdint.h>
    
    
    #define  ACCUM_SIZE  16   // Passed in as -D gcc parameter. (Min=9, Max=64) Bit width of generated random numbers.
    #define  CONSTANT_A  14   // Passed in as -D gcc parameter.
    #define  CONSTANT_B  2    // Passed in as -D gcc parameter.
    #define  CONSTANT_C  7    // Passed in as -D gcc parameter.
    
    
    #define  ACCUM_MASK  (((1ULL<<(ACCUM_SIZE-1))-1)<<1|1)   // Bit of a shuffle to work on all 64 bits :)
    
    
    // Seed the state array.  Seed MUST not be all zero.
    static uint64_t  s[2] = {1, 0};
    
    
    static inline  uint64_t rotl(uint64_t value, int shift) {
    	return ((value << shift) | ((value & ACCUM_MASK) >> (ACCUM_SIZE - shift))) & ACCUM_MASK;
    }
    
    
    static uint64_t  next(void) {
    	uint64_t  s0 = s[0];
    	uint64_t  s1 = s[1];
    	uint64_t  result = (s0 + s1) & ACCUM_MASK;
    
    	s1 ^= s0;
    	s[0] = rotl(s0, CONSTANT_A) ^ s1 ^ (s1 << CONSTANT_B) & ACCUM_MASK;
    	s[1] = rotl(s1, CONSTANT_C);
    
    	return result;
    }
    
    
    
    //  Store high 8 bits of generated numbers.
    int  main(int argc, char* argv[])
    {
    	uint64_t  random64;
    	int  i = 20;
    
    
    	// Print some randomness
    	while(i--)
    	{
    		random64 = next();
    		printf( "%04lx ", random64 );
    	}
    	printf("\n");
    
    	return 0;
    }
    
  • evanhevanh Posts: 15,915
    Oh, the above 20 sums is full 16 bits, ie: The LSbit is included.
  • evanhevanh Posts: 15,915
    Here's what I get using Chip's simple example without any masking/clearing of the summing register:
    evanh@control:~/hoard/Propeller/Prop2/testing$ ../loadp2 -v -t xoro32-seq20.obj
    Searching serial ports for a P2
    P2 version A found on serial port /dev/ttyUSB0
    Loading xoro32-seq20.obj - 1216 bytes
    xoro32-seq20.obj loaded
    [ Entering terminal mode. Press ESC to exit. ]
    00000001 00804085 42a05530 18282c7c 3e06769f 4f83a248 a30edffd f0d0202d c8eff2f1 76f25aca 944b4dc8 9a16d1d1 d6d7adcd 10810598 cc731b30 66418094 093e540c f822d6a4 51139c9d 4c8e2eac
    You can see, ignoring the upper 16 bits, the lower 16 bits are a match.
  • TonyB_TonyB_ Posts: 2,178
    edited 2017-09-22 22:06
    evanh wrote: »
    Here's a hack up of old testing code (ie: Not the actual Prop2's XORO32):
    evanh@control:~/hoard/rng_testing$ gcc -o seq20-xo "src/xoroshiro128plus-seq20.c" -O3
    evanh@control:~/hoard/rng_testing$ ./seq20-xo
    0001 4085 5530 2c7c 769f a248 dffd 202d f2f1 5aca 4dc8 d1d1 adcd 0598 1b30 8094 540c d6a4 9c9d 2eac

    Many thanks, Evan.

    If not done already, xoroshiro32+ is now working on the Z80! :)

    64 x 384 - 2K
  • evanhevanh Posts: 15,915
    Hehe, I'm guessing you might just be the first.
  • And with those comparison results, I think I can claim first implementation on the 6502.
    8)
  • evanhevanh Posts: 15,915
    Lol, you guys aren't really going to use that for anything are you? Are there active source repositories for 6502/Z80? Surely not.
  • Lots of people still use the Z80. Dunno about the "6502" whatever that is ... :)

    Any chance Evan of the first few XORO34 sums for triplet [7,8,12] when seed = 1? I'm now writing a Z80 version of that. Sorry I don't use C and an independent data check would be much appreciated.
  • kwinnkwinn Posts: 8,697
    evanh wrote: »
    Lol, you guys aren't really going to use that for anything are you? Are there active source repositories for 6502/Z80? Surely not.

    Evan, you would be surprised at how much source code for the 6502, 6800, and Z80 is still around. In addition to the computer enthusiasts there are also quite a few pieces of equipment that use those chips still in service. They may no longer be state of the art but they are rugged, reliable, and work almost as well as a lot of new equipment.
  • WDC ships a ton of 6502 variants, many 8bit, every year.

    It sees a ton of use in toys, local microcontrollers, small scale embedded...

    I'm sure the Z80, others are similar. I wonder about the 6809. That one is beautiful. Best 8 bit ever made, IMHO.

    At higher clocks possible today, those designs can respond very quickly, library code is debugged, known cold, just works, and tools are stable too.

    Simple, fast, cheap. Just not big.
  • The 65xx brand is probably the only processor family that has remained loyal to its ISA over the last 33 years. In addition it has served the widest spectrum of electronic markets through those years. For example, it has served and in some cases created markets for the PC, video game, toy, communication, industrial control, automotive, life support embedded in the human body medical devices, outside the body medical systems, engineering education systems, hobby systems, and you name it electronic market segments. I might add the 65xx has served in a highly reliable and successful way!

    http://www.westerndesigncenter.com/wdc/

    They talk about 200 mhz options! ASIC and FPGA.

    That gets one into an ISR in about 35ns. A read, respond cycle expectation might be 100ns.

  • kwinnkwinn Posts: 8,697
    potatohead wrote: »
    .......

    I wonder about the 6809. That one is beautiful. Best 8 bit ever made, IMHO.........

    I agree. Such a nice architecture and orthogonal instruction set.
  • evanhevanh Posts: 15,915
    For sure, they're still used as pre-existing embedded cores still doing the same job as before, Casio G-Shock watches sticks out in my mind here (I actually wonder if Casio even have any software engineering team at all), but is anyone using them to build new stuff that would use newer algorithms/techniques?
  • There is an active Apple II community still developing new software, the chicken lips (C=) and Atari communities are still quite active, and I'm sure there are other vintage computer communities still developing for the 6502 and Z80.

    An algorithm like this could be used standalone or to support interaction of Prop 2 projects with software written for the legacy hardware to provide new grist for the mill of hobbyists.

    Many of these communities are doing these things not for the next big thing, but because they can....

    A few examples:
    lawlesslegends.com
    6502workshop.com/p/nox-archaist.html
  • evanhevanh Posts: 15,915
    TonyB_ wrote: »
    Any chance Evan of the first few XORO34 sums for triplet [7,8,12] when seed = 1? I'm now writing a Z80 version of that. Sorry I don't use C and an independent data check would be much appreciated.
    I reckon the best approach there is a Xoroshiro40+ implementation. That would fully use the 5th byte of state storage. I've got the scores for that word size also. I'll dig them up when I get home ...
  • TonyB_TonyB_ Posts: 2,178
    edited 2017-09-29 01:13
    Thanks a lot, Evan. Actually, the XORO34 constant 8 makes the xor-ing simpler than XORO32 and saves the use of an 8-bit register, which helps with manipulating the extra two state bits.
  • evanhevanh Posts: 15,915
    First twenty 17-bit (Xoroshiro34) sums for triplet [7,8,12] is:
    00001 01181 1608d 0a75d 0bf68 1c71d 158e8 028f2 1c4a8 1c24f 14e6c 1f938 1f135 07a8e 068cd 15404 1d908 02648 1e45c 13161

    First twenty 20-bit (Xoroshiro40) sums for triplet [7,9,12] is:
    00001 01281 c6013 5a2f1 2f5ac 7590c fb594 b7ac1 2a644 33649 ebe23 66f73 18a54 fd4a2 4674a 590d3 37bc4 2cce9 3a9db 0ee4e

    [7,9,12] was chosen from below scores:
        Xoroshiro40+ PractRand Score Table
    
    Combination    Word1   Word2  Byte12  Byte06   Byte2   Byte1    Bit
    ====================================================================
     [ 1  7  8]      4M      4M     64M     64M      4M      1M    256G
     [ 1 16 14]      2M      2M     64K     64K    128K    128K    256G
     [ 2  1 19]    128K     64K     32K     32K     64K     64K    256G
     [ 2  7  3]     16M     32M      8M      8M    512K    256K    256G
     [ 2 16  3]      2M      4M    512K    256K    256K    256K    256G
     [ 2 18  5]      8M      8M      8M      1M      1M      1M    256G
     [ 3  2  8]     64M     64M    512M    128M     64M     64M    128G
     [ 3  7  2]      2M      4M      4M    128K    128K    128K     16M
     [ 3 10 14]    256M    128M     16G    256K    512K    256M    256G
     [ 3 16  2]    256K    256K    128K     64K     64K     32K    256G
     [ 4  2 19]      2M      2M    256K    256K    256K    256K    256G
     [ 4  3 15]     32M     64M      1M      1M      2M    256M    256G
     [ 4  4 15]     32M     32M      1M      1M      2M     16M     64G
     [ 4  9  5]    512M      1G    128M     16M      8M      4M    256G
     [ 4 19 19]      2M      2M    512K    512K    512K    512K    256K
     [ 5  2  8]      2G      2G    128M    128M     64M     64M    256G
     [ 5  2 18]     64M     32M      1M    512K      1M      2M    256G
     [ 5  9  4]      8M     16M     16M      1M    128K    128K    256M
     [ 5 16  6]    256M    256M    128G     16M     16M     16M    256G
     [ 5 18  2]      4M      4M    512K    512K    512K    512K    256G
     [ 6  3 17]    256M    512M      1M      2M      4M    256M    256G
     [ 6 10 17]      2G      4G     32G     32M     64M    256M    256G
     [ 6 14 11]      2G      2G      8G      8G      8G    256M    256G
     [ 6 16  5]      2M      4M      8M    128K    128K    128K    256G
     [ 6 16  9]      2G      2G      1G      1G      2G    256M    256G
     [ 7  1 14]      1G      1G    256M    512M    512M    256M    256G
     [ 7  2 14]     16G      8G    256M    512M      4G    256M     64G
     [ 7  9 12]     16G     16G     64G     32G     32G    256M    256G
     [ 8  2  3]    512M    256M      4M      4M      8M     16M     16M
     [ 8  2  5]    128M    256M      4M      4M      8M      8M     32M
     [ 8  5  9]      1G      1G      1G      1G      8G    256M    256G
     [ 8  7  1]      8M      4M      1M      1M      1M      1M     16M
     [ 8  8 11]    128M    128M    128M    128M      1G    256M    256G
     [ 8 13  9]      1G      2G      8G      4G    128G    256M    256G
     [ 9  5  8]     32M     64M      8M      8M     32M    256M    256M
     [ 9 13  8]      8M      8M      2G      1G      4G    256M     64G
     [ 9 16  6]     64M     64M    512M      8M     16M    256M    256G
     [10  9 17]     32M     64M      1G      1G    512M    256M    256G
     [11  8  8]      8M      8M      4M     32M    128M    256M      2G
     [11 13 16]      2G      2G     32G      8G     64G    256M    256G
     [11 14  6]      2G      2G     16G     32M      8G    256M    256G
     [12  3 13]      4G      4G    128G     16G     64G    256M    256G
     [12  6 17]      8G      8G    128G    128G     16G    256M    256G
     [12  9  7]      2G      1G     64M     64M     64G    256M      4G
     [12 18 13]    512M    512M    128G     32G     64G    256M    256G
     [13  3 12]     64M    128M      2G      2G     32G    256M     64G
     [13 18 12]      4M      4M     16G      4G      2G    256M    256G
     [14  1  7]    512M    512M    512M      4G      2G    256M     64G
     [14  2  7]     32G     32G      1G      4G      4G    256M     64G
     [14 10  3]      2G      4G      8G    128M     64M    256M     64G
     [14 16  1]    128M    128M     32M     32M     16M      8M    256G
     [15  3  4]      4G      4G    256M    256M    256M    256M    256G
     [15  4  4]     64M     64M      8M     32M     16M     16M    256G
     [15  5 18]      2G      2G      4G    128M     16M      8M    256G
     [16 13 11]      1G      1G    128G     32G     64G    256M    256G
     [17  1 18]     32M     32M     16M     16M     16M     16M    256G
     [17  3  6]    512M    512M      2G      1G      1G    256M    256G
     [17  6 12]      8G      8G     64G     64G     64G    256M    256G
     [17  9 10]      4G      4G      4G     16G      2G    256M    256G
     [17 10  6]      4G      8G     16G      2G      8G    256M    256G
     [18  1 17]    512K      1M    128K    128K     64K     64K    256G
     [18  2  5]      2G      2G      1G    512M    512M    256M    256G
     [18  5 15]      2G      2G      2G    256M    256K    256K    256G
     [19  1  2]      2M      2M    512K    512K    512K    256K    256G
     [19  2  4]     64M     64M     64M     64M     64M     64M    256G
     [19 19  4]    128M    128M     32M     32M     32M     32M    256G
    
  • evanhevanh Posts: 15,915
    edited 2017-09-29 07:38
    BTW: It is notable that, up at this word size, bit 1 is also dropping in quality compared to the higher bits. (Bit 0 is not in any of the scores).

    EDIT: Although, even though that would easily explain the byte1 sample variant, it is also contradicted by the word2 variant hardly deviating from the word1 variant. (Word1 and byte1 includes bit 1, while word2 and byte2 doesn't.)
  • TonyB_TonyB_ Posts: 2,178
    edited 2017-09-29 12:52
    evanh wrote: »
    First twenty 17-bit (Xoroshiro34) sums for triplet [7,8,12] is:
    00001 01181 1608d 0a75d 0bf68 1c71d 158e8 028f2 1c4a8 1c24f 14e6c 1f938 1f135 07a8e 068cd 15404 1d908 02648 1e45c 13161

    First twenty 20-bit (Xoroshiro40) sums for triplet [7,9,12] is:
    00001 01281 c6013 5a2f1 2f5ac 7590c fb594 b7ac1 2a644 33649 ebe23 66f73 18a54 fd4a2 4674a 590d3 37bc4 2cce9 3a9db 0ee4e

    Many thanks, Evan. You are a star! :)
  • TonyB_TonyB_ Posts: 2,178
    edited 2017-09-29 16:36
    Not counting the seed/2=0, here are the top 16 bits of the first sixteen Xoroshiro34 sums for triplet [7,8,12]:

    08C0 B046 53AE 5FB4 E38E AC74 1479 E254 E127 A736 FC9C F89A 3D47 3466 AA02 EC84

    My Z80 code matched the first four first time but 5th sum was EB4E then the rest went very pear-shaped. I hate it when something half works. I prefer total failure! At least I'm on the right track.
  • evanhevanh Posts: 15,915
    When I worked on the generic version I missed a critical masking of the input "value" variable in the rotl() function. That caused a lot of garbage in my early scores before I was even using full period candidates.

    What would happen is any extra overhang in the input would be immediately right-shifted into the working rang and therefore contaminate the sequence.

    Funnily, now that the state bits don't have any bleed, that mask probably isn't strictly needed.
  • Changing one instruction from RRCA to RRA solved the Z80 problem. Assembled with M80, linked with L80, program runs fine in CP/M. I also claim first use of QuickBASIC for generating xoroshiro states and sums. Welcome to Retroland! :)
Sign In or Register to comment.