
MessageID: <20140420150839.GA19097@openwall.com> Date: Sun, 20 Apr 2014 19:08:40 +0400 From: Aleksey Cherepanov <aleksey.4erepanov@...il.com> To: johnusers@...ts.openwall.com Subject: one decimal digit adder using rules (2+3 > 5) I made an adder using rules. It works for 2 numbers of 1 decimal digit each. I'll describe two approaches. 1) Make a lot of rules like "if digit1 is ... and digit2 is ... then ...". To express statement like "if condition then action1 else action2" one could use two rules: reject if not condition, action1 reject if condition, action2 So I made 100 rules like the following: /+ {\[} M \[ /2 X010 \] /3 Az"5" \[ /+ {\[} # drop +, so 2+3 > 23 M \[ # remember digits and drop the first /2 # reject input where the second digit is not equal to 2 X010 \] # put the first digit back and drop the second /3 # reject input where the first digit is not equal to 3 Az"5" \[ # put result into the word and drop second digit So 2, 3 and 5 should be varied. Here is a oneliner to do the job: perl e 'for $i (0 .. 9) { for $j (0 .. 9) { $c = $i + $j; print qq#/+ {\\[} M \\[ /$i X010 \\] /$j Az"$c" \\[\n# }}' This variant handles carry. 2) Somehow transform digits to join them without rejects. We could use dummy values to avoid rejects but still have branching when we use search. I'll subtract 1 from the first digit and add 1 to the second digit many times. Loops could be expressed being just unrolled: I search for 9, replace it with 8 and add 1 to the second digit, then I search for 8, replace it with 7 and add 1 to the second digit, and so on. Dummy values could be used to make variable amount of effective iterations: I add "9a", so some first iterations work on the dummy part. I encode the second digit so it is messed with the first digit in case of "233f". Iterations /3 ... and /2 ... could look like: 2t3i 2t2o 1y2o The rule: /+ {\[} M s0w s1e s2r s3t s4y s5u s6i s7o s8p s9\[ \[ X010 Az"9a" va01 /9 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /8 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /7 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /6 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /5 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /4 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /3 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /2 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /1 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc sw0 se1 sr2 st3 sy4 su5 si6 so7 sp8 s\[9 \[ \]\] /+ {\[} # drop +, so 2+3 > 23 # Then we replace the second digit like "12...9" > "we...[" to # protect it from search for digits. M s0w s1e s2r s3t s4y s5u s6i s7o s8p s9\[ \[ X010 Az"9a" # Add dummy, so search 9 does not fail anyway va01 # Store 1 to make p+1 later # The main block: /9 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc ... /1 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc # In detail (the tail is described later): /9 # Search for digit, it may be actual digit or dummy vbp0 vcba # Store position and position+1 R M L Dc Xc1c # Shift right (by keyboard) the second digit: d++ L M R Xb1b Dc # Shift left (by keyboard) the first digit: d # The tail: sw0 se1 sr2 st3 sy4 su5 si6 so7 sp8 s\[9 # Reverse protective encoding \[ \]\] # Cut the first digit and dummy out # The end Commands to try: echo 2+3  ./JohnTheRipper/run/john ru=my pipe stdout for i in $(seq 0 9); do for j in $(seq 0 9); do printf "$i + $j = "; echo "$i+$j"  ./JohnTheRipper/run/john ru=my pipe stdout 2>/dev/null; done; done When results if higher than 9 we get ]. No carry in this implementation. It would be easier to put values directly but only the first digit could be transformed that way. It does not look like rules have good primitives to make efficient adder. Though one could try to use cases as bits (TN toggles bit at position N). It should be interesting to try. Also one should be able to use M and variables to implement a stack: push: store length, add memorized value to the current one, remember, remove added value. Problems I had:  I was really confused about XNMI rules, somehow I thought M is the second position but X000 did not work and my rules worked very strange. But M is the length. Maybe doc/RULES could tell about it earlier near "substring NM".  Shifts are limited, so L does not shift 'a' and R does not shift '\'. So my temporary shifts broke values with wrong encoding. That's why I use wer... and not asd...  Shifts could not be applied to a single position so I had to use construction like: shift M shift_back Dp Xp1p. Thanks!  Regards, Aleksey Cherepanov
Powered by blists  more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.