Brad Forschinger

Saturday, December 5, 2020

hard reset a Nokia 800 Tough

This phone freezes from time to time. Holding down Power and Right Select (-) will reboot the phone. This doesn't seem to be documented in the manual.

Tuesday, August 4, 2020

The Intel Atom CPU with earlier Synology units does not have VT-x extensions 1, and using KVM will fall back to full (slow) emulation. These units do provide a way to run workloads via Docker, however, and we can instead paravirtualize with User Mode Linux inside a container. You can read more about UML in Jeff Dike's book 2. I won't detail configuring UML here, I will only present what I am using.

Firstly, create a container to bootstrap the image. I used rdebath-devuan:beowulf, and then added a folder into the container from the Synology. Go to Docker > Container > [NAME] > Edit > Volume and then "Add Folder", mount it at /mnt. You will use this same volume to provide the disk for your VM to boot from. Once you start the container, change to the Terminal pane. Run the following:

# debootstrap beowulf /mnt/a
# chroot /mnt/a tasksel openssh-server
# cat > /mnt/a/etc/network/interfaces <<_EOF_
auto eth0
  iface eth0 inet static
  address 10.0.2.15/32
  up ip route add default dev eth0
_EOF_
# cat > /mnt/a/root/.ssh/authorized_keys <<_EOF_
...
_EOF_
# mkfs.ext4 /mnt/a.img -d /mnt/a 10G

Once this finishes, you'll have a filesystem ready to boot. Create a new Docker container, example Dockerfile:

FROM rdebath/devuan:beowulf
RUN apt -y update && apt -y install user-mode-linux slirp
COPY run-slirp.sh /run-slirp.sh
VOLUME ["/disks"]
VOLUME ["/dev/shm"]
ENTRYPOINT ["linux"]
CMD ["mem=512M","ubda=/disks/a.img","con=pts","con0=fd:0,fd:1","con1=none","umid=devuan","eth0=slirp,,/run-slirp.sh","net.ifnames=0"]
EXPOSE 22

Where /run-slirp.sh is:

#!/bin/sh
exec /usr/bin/slirp-fullbolt "redir 22 22"

Create a volume to be mounted at /dev/shm, the ssh into your Synology and mount it as tmpfs. This is a bit hacky, but you'll need to have scratch space available for UML. Also mount the volume you created earlier, mine's at /disks. Once you bring the container up you will see the kernel boot messages in the terminal in Synology's web interface. You can then ssh into the port you exposed, with the key you supplied. And, looking at the "cpu":

$ cat /proc/cpuinfo
processor       : 0
vendor_id       : User Mode Linux
model name      : UML
mode            : skas
host            : Linux devuan 3.10.105 #25426 SMP Wed Jul 8 03:16:31 CST 2020 x86_64
bogomips        : 2092.23

Enjoy!

Sunday, April 12, 2020

bit string permutations with sed(1)

Consider an alphabet with symbols {0,1}, how can we cycle through all permutations? How might we do it with regular expressions?

An example, for w = 2:

1. (00) = (00)
2. (01) = (01), (10)
3. (10) = (01), (10)
4. (11) = (11)

Discarding the simple cases of 1 and 4, we can start to see that we need to also think about the order of the generation for a given starting point. HAKMEM #175 produces these in lexicographic order by due to the cascading effect of addition, but strings are generally read left to right. So, a reflected ordering is perhaps the most straightforward approach here:

sed -n ':p; p; s/^\(1*\)\(0*\)01/\2\110/; tp;'

which produces, in reverse colexicographic (!) order, the permutations of the string. For w = 4, and (0011):

$ echo 0011 | sed -n ':p; p; s/^\(1*\)\(0*\)01/\2\110/; tp;'
0011
0101
1001
0110
1010
1100
$

Note we can rev(1) and tac(1) to put it into lexicographic ordering. However, if we instead choose to invert the symbol replacement in sed(1), we can do reflected ordering at which point it's enough to pipe through rev(1).

01 ⇒ 10 transformations, reverse colexicographic order

$ (echo rev-colex lex colex rev-lex; echo sed tac-rev tac rev
> (echo 0011 |
> sed -n ':p; p; s/^\(1*\)\(0*\)01/\2\110/; tp;' |
> tee >(rev) >(tac) >(tac|rev) | pr -t4)) | column -t
rev-colex  lex      colex  rev-lex
sed        tac-rev  tac    rev
0011       0011     1100   1100
0101       0101     1010   1010
1001       0110     0110   1001
0110       1001     1001   0110
1010       1010     0101   0101
1100       1100     0011   0011
$

10 ⇒ 01 transformations, colexicographic order

$ (echo colex rev-lex rev-colex lex; echo sed tac-rev tac rev
> (echo 1100 |
> sed -n ':p; p; s/^\(0*\)\(1*\)10/\2\101/; tp;' |
> tee >(rev) >(tac) >(tac|rev) | pr -t4)) | column -t
colex  rev-lex  rev-colex  lex
sed    tac-rev  tac        rev
1100   1100     0011       0011
1010   1010     0101       0101
0110   1001     1001       0110
1001   0110     0110       1001
0101   0101     1010       1010
0011   0011     1100       1100
$

Stay safe!

Sunday, April 28, 2019

CMWCs in mod w+1

While re-reading TAoCP Volume 2, there's a curious passage during the discussion of mod +/- 1 LCGs regarding the use of x_{n}=a*x_{n-1}+c, which states: "For reasons to be explained later, we will generally want c=0 when m=w+1, so we merely need to compute (aX) mod (w+1)". After a few hours I can understand why. For LCGs it's not so dire, because we can treat 0 simply as w+1, because no operation will result in 0. I touched on this topic a few years ago at [1] for LCGs (mod w+1), and [2] for MWC and CMWCs (mod w-1).

For the case of CMWCs, it's beneficial for us to use use w-1. As noted by Marsaglia, this is because we can have w-1 as a primitive root. Briefly, with g as w-1 and n as a*g+1, g^{phi(n)/f} != 1 for all factors of phi(n). This is made easier when n is prime, because phi(n)=n-1. When n is composite, more work is required for establising the order: we need to find the least common multiple across the order of all the factors.

With w-1=65535, let's consider an a of 65518 (as used in [1]), and then arbitrarily its neighbour 65517.

# 65518*65535+1
65535^{4293722130/2} mod 4293722131 == 4293722130
65535^{4293722130/3} mod 4293722131 == 1070428133
65535^{4293722130/5} mod 4293722131 == 3696002153
65535^{4293722130/17} mod 4293722131 == 2477700139
65535^{4293722130/41} mod 4293722131 == 2876866897
65535^{4293722130/47} mod 4293722131 == 1432659653
65535^{4293722130/257} mod 4293722131 == 1579676435

... which indeed has a period of 4293722130, and we needn't look further because none of the results are 1. However, for the composite 65517*65535+1 we need to perform an exhaustive search.

# 65517*65535+1
65535^{1036399840/2} mod 4293656596 == 1
65535^{1036399840/5} mod 4293656596 == 1
65535^{1036399840/7} mod 4293656596 == 3849485225
65535^{1036399840/19} mod 4293656596 == 318890497
65535^{1036399840/113} mod 4293656596 == 3330338425
65535^{1036399840/431} mod 4293656596 == 2842235365

Walking the generator gives the period `12954998`. Now, to prove it we need to do something like:

n = 4293656596
# 4293656596: 2 2 29 37014281
# ...
# 1:
# 1:
# 28: 2 2 7
# 37014280: 2 2 2 5 19 113 431

# product of 28 and 37014280's factors
phi_n = 1036399840
for f in [2,5,7,19,113,431]:
print '# factor',f
for x in xrange(1,phi_n/f):
if pow(65535,f*x,n) == 1:
print(f, x)
break

# (2, 6477499)
# (5, 12954998)
# (7, 1850714)
# (19, 681842)
# (113, 114646)
# (431, 30058)

and then the least common multiple of the orders:

>>> reduce(lcm,(6477499,12954998,1850714,681842,114646,30058))
12954998

Bingo. Now, returning to Knuth's quote. There is indeed some more work to be done with w+1 when we consider c != 0, but not a lot more than handling w-1. The catch with using w+1, is that we'll always lose at least a factor of 2 for our order because of word sizes being 2^n. So, adjusting for w+1 doesn't actually give us a CMWC of longer period than MWC, but CMWCs do have other nice properties such as always being a multiple of the base for instance. While CMWCs in base 2^n will at least lose a factor of 2^4, 2^n+1 can optimally lose 2^1.

With 2^n+1=65537 here, we can use the following code to generate the expansion 65514*65537+1 with a period of `2146795509`. We handle the case of a real zero by stepping to the next state, ensuring the 0=256 mapping.

rand proc near
push dx
mov dx,65514
db 0xb8 ; mov ax,imm16
x dw 1
mul dx
db 0x05 ; add ax,imm16
c dw 1
adc dx,0

; handle wrap
sub ax,dx
ja done
jnz wrap

; skip an actual 0
xchg ax,dx
mov dx,65514
sub ax,dx
wrap: inc ax
dec dx

done: neg ax ; (b-1-x) == 0-x == neg ax
mov cs:[x],ax
mov cs:[c],dx
pop dx
ret
rand end

I wrote it for density, not performance. Modern processors will invalidate their I$ if modified, resulting in a performance hit. Changing the self-modifying code to point x and c into a data section is left as an exercise for the reader.

[1] - https://b2d-f9r.blogspot.com/2010/10/lcg-mod-65537.html
[2] - https://b2d-f9r.blogspot.com/2010/11/multiply-with-carry-generator-in-16-bit.html

Wednesday, July 26, 2017

huffman routines for shell

For bash or ksh, with strings of [a-z]. Using base-36 to pluck the bitstrings out of huff[], has the added bonus of flattening the case for you. As such:

$ _decode $(_encode tHeQuIcKbRoWnFoX)
thequickbrownfox
$