Brad Forschinger

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)

# (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))

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
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] -
[2] -

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)


_encode() {
  typeset in="${1:?args}"
  typeset out=""
  typeset huff=(
    1110      101100    01000   11111       # a b c d
    011       00110     111100  0101        # e f g h
    1100      001011001 0010111 10111       # i j k l
    00111     1010      1101    101101      # m n o p
    001011010 1000      1001    000         # q r s t
    01001     001010    111101  001011011   # u v w x
    00100     001011000                     # y z
  typeset -i i=0

  while (( i < ${#in} )); do
    out+="${huff[36#${in:i++:1} - 10]}";

  echo "${out}"

_decode() {
  typeset d="${1:?args}"
  typeset out=""

  while [[ "$d" ]]; do
    d="${d/#000/t}"        d="${d/#011/e}"        d="${d/#0101/h}"       \
    d="${d/#1000/r}"       d="${d/#1001/s}"       d="${d/#1010/n}"       \
    d="${d/#1100/i}"       d="${d/#1101/o}"       d="${d/#1110/a}"       \
    d="${d/#00100/y}"      d="${d/#00110/f}"      d="${d/#00111/m}"      \
    d="${d/#01000/c}"      d="${d/#01001/u}"      d="${d/#10111/l}"      \
    d="${d/#11111/d}"      d="${d/#001010/v}"     d="${d/#101100/b}"     \
    d="${d/#101101/p}"     d="${d/#111100/g}"     d="${d/#111101/w}"     \
    d="${d/#0010111/k}"    d="${d/#001011000/z}"  d="${d/#001011001/j}"  \
    d="${d/#001011010/q}"  d="${d/#001011011/x}"


  echo "${out}"

Monday, September 7, 2015

epoch when your date(1) doesn't understand +%s

10# given to force base 10, bash will attempt to be clever on zero-led numbers whereas ksh always assumes base 10.

toepoch() {
  local -i Y=10#${1:?} m=10#${2:?} d=10#${3:?} H=10#${4:?} M=10#${5:?} S=10#${6:?}

  if ((m > 2)); then
    let m-=3
    let m+=9
    let --Y

  local -i c='Y / 100'
  local -i ya='Y - 100 * c'

  local -i j='
    (146097 * c)  / 4 +
    (1461 * ya)   / 4 +
    (153 * m + 2) / 5 +
  local -i result='((j - 719469) * 86400) + (H * 3600) + (M * 60) + S'

  echo $result

Can be then run as: toepoch $(date -u "+%Y %m %d %H %M %S")

Monday, August 24, 2015

WYYC 2015 1A results

1final1Zach GormleyUnited Statesfinal semi-final
2final2Shion ArayaJapanfinal semi-final prelim
3final3Iori YamakiJapanfinal semi-final
4final4Takeshi MatsuuraJapanfinal semi-final
5final5Yusuke OtsukaJapanfinal semi-final prelim
6final6Gentry SteinUnited Statesfinal
7final7Ryuichi NakamuraJapanfinal semi-final prelim
8final8Luis Enrique VillasenorMexicofinal semi-final
9final9Akitoshi TokubuchiJapanfinal semi-final prelim
10final10Janos KaranczHungaryfinal semi-final
11final11Anthony RojasUnited Statesfinal semi-final
12final12Marcus KohSingaporefinal semi-final
13final13Yamato MurataJapanfinal semi-final prelim
14final14Ahmad KharismaIndonesiafinal semi-final
15final15Hiroyuki SuzukiJapanfinal semi-final
16final16Jakub DekanCzech Republicfinal semi-final
17final17Colin BeckfordUnited Statesfinal semi-final prelim wildcard
18final18Ryota OgiJapanfinal semi-final prelim
semi-final1Ryuichi NakamuraJapanfinal semi-final prelim
semi-final2Shion ArayaJapanfinal semi-final prelim
semi-final3Iori YamakiJapanfinal semi-final
semi-final4Yusuke OtsukaJapanfinal semi-final prelim
semi-final5Yamato MurataJapanfinal semi-final prelim
semi-final6Luis Enrique VillasenorMexicofinal semi-final
semi-final7Janos KaranczHungaryfinal semi-final
semi-final8Anthony RojasUnited Statesfinal semi-final
semi-final9Ahmad KharismaIndonesiafinal semi-final
semi-final10Hiroyuki SuzukiJapanfinal semi-final
semi-final11Zach GormleyUnited Statesfinal semi-final
semi-final12Takeshi MatsuuraJapanfinal semi-final
semi-final13Marcus KohSingaporefinal semi-final
semi-final14Akitoshi TokubuchiJapanfinal semi-final prelim
semi-final15Ryota OgiJapanfinal semi-final prelim
semi-final16Jakub DekanCzech Republicfinal semi-final
semi-final17Colin BeckfordUnited Statesfinal semi-final prelim wildcard
19semi-final18Izuru HasumiJapansemi-final prelim wildcard
20semi-final19Benson FokHong Kongsemi-final prelim wildcard
21semi-final20Andrew MaiderUnited Statessemi-final
22semi-final21Kazuki OkadaJapansemi-final prelim
23semi-final22Jason Liu ZichenChinasemi-final
24semi-final23Ayumu HaradaJapansemi-final prelim wildcard
25semi-final24Shinya KidoJapansemi-final prelim wildcard
26semi-final25Luckey Li Yu LinCanadasemi-final
27semi-final26Peter PongHong Kongsemi-final
28semi-final27Toya KobayashiJapansemi-final prelim wildcard
29semi-final28Vilmos Zoltan KissHungarysemi-final
30semi-final29Matous TomesCzech Republicsemi-final prelim
31semi-final30Ky ZizanUnited Statessemi-final
32semi-final31Paul KerbelMexicosemi-final
33semi-final32Eric Tran-TonUnited Statessemi-final prelim wildcard
34semi-final33Kuo Tzu WeiTaiwansemi-final
35semi-final34Kento MuraokaJapansemi-final prelim wildcard
36semi-final35Carlos BraunGermanysemi-final
37semi-final36Daniel BorgesBrazilsemi-final
38semi-final37Jeremy TanSingaporesemi-final prelim
39semi-final38Christopher ChiaSingaporesemi-final prelim
40semi-final39Kazuya MurataJapansemi-final prelim wildcard
41semi-final40Chen YangChinasemi-final prelim
42semi-final41Weichuan WangChinasemi-final prelim wildcard
43semi-final42Tsukasa NambaJapansemi-final prelim wildcard
44semi-final43Brandon VuAustraliasemi-final
45semi-final44Zafran AqilMalaysiasemi-final
46semi-final45Min Chan-HongRepublic of Koreasemi-final
47semi-final46Arif RamadhanIndonesiasemi-final prelim
48semi-final47Yuji KellyUnited Kingdomsemi-final
prelim1Shion ArayaJapanfinal semi-final prelim
prelim2Ayumu HaradaJapansemi-final prelim wildcard
prelim3Christopher ChiaSingaporesemi-final prelim
prelim4Ryuichi NakamuraJapanfinal semi-final prelim
prelim5Izuru HasumiJapansemi-final prelim wildcard
prelim6Yusuke OtsukaJapanfinal semi-final prelim
prelim7Yamato MurataJapanfinal semi-final prelim
prelim8Chen YangChinasemi-final prelim
prelim9Colin BeckfordUnited Statesfinal semi-final prelim wildcard
prelim10Toya KobayashiJapansemi-final prelim wildcard
prelim11Akitoshi TokubuchiJapanfinal semi-final prelim
prelim12Benson FokHong Kongsemi-final prelim wildcard
prelim13Shinya KidoJapansemi-final prelim wildcard
prelim14Kazuki OkadaJapansemi-final prelim
prelim15Kazuya MurataJapansemi-final prelim wildcard
prelim16Ryota OgiJapanfinal semi-final prelim
prelim17Matous TomesCzech Republicsemi-final prelim
prelim18Tsukasa NambaJapansemi-final prelim wildcard
prelim19Kento MuraokaJapansemi-final prelim wildcard
prelim20Jeremy TanSingaporesemi-final prelim
prelim21Eric Tran-TonUnited Statessemi-final prelim wildcard
prelim22Arif RamadhanIndonesiasemi-final prelim
prelim23Weichuan WangChinasemi-final prelim wildcard
49prelim24Masahiro TeradaJapanprelim
50prelim25Paolo BuenoUnited Statesprelim
51prelim26PiscoChinaprelim wildcard
52prelim27Ryota KomatsuJapanprelim wildcard
53prelim28Kenta KushiroJapanprelim wildcard
54prelim29Tatsuaki OkamotoJapanprelim wildcard
55prelim30Clint ArmstrongUnited Statesprelim wildcard
56prelim31Kevin NicholasUnited Statesprelim wildcard
57prelim32Park Woo-ChanRepublic of Koreaprelim
58prelim33Konstantin TudjarovBulgariaprelim
59prelim34Takumi SakamotoJapanprelim wildcard
60prelim35Yuya YataniJapanprelim wildcard
61prelim36Hiroaki YoshiiJapanprelim wildcard
62prelim37Tomas BubakCzech Republicprelim
63prelim38Tatsuya FujisakaJapanprelim
64prelim39Chow ChakronChinaprelim
65prelim40Yuki NishisakoJapanprelim wildcard
66prelim41Harrison LeeCanadaprelim
67prelim42Cha Dam-DaeRepublic of Koreaprelim
68prelim43Evan NagaoUnited Statesprelim
69prelim44Robert KuceraCzech Republicprelim
70prelim45Emil WojcikUnited Kingdomprelim
71prelim46Keiran CooperCanadaprelim
72prelim47Li Ho KwanHong Kongprelim
73prelim48Ryo IgarashiJapanprelim wildcard
74prelim49Petr KavkaCzech Republicprelim
75prelim50Jeong Yong-ChanRepublic of Koreaprelim
76prelim51Ilya MatrosRussiaprelim
77prelim52Jack Wong Wai KitHong Kongprelim
78prelim53Pall GudmundssonIcelandprelim
79prelim54Zhao ChenChinaprelim
80prelim55Daiki TanakaJapanprelim wildcard
81prelim56Orlando AbrajanMexicoprelim
82prelim57Ethan WongHong Kongprelim
83prelim58Koyo HashimotoJapanprelim wildcard
84prelim59Hobbit-Wen WangTaiwanprelim
85prelim60Michael KurtiUnited Statesprelim
86prelim61Winky LeonMacauprelim
87prelim62Tomoki ToyamaJapanprelim wildcard
88prelim63Yuki ShigematsuJapanprelim wildcard
89prelim64Lucas GremlerUnited Statesprelim wildcard
90prelim65Sergio LiconaMexicoprelim
91prelim66Sean HungSingaporeprelim
92prelim67Ryosuke HaraJapanprelim wildcard
93prelim68Aiman RohishamMalaysiaprelim
94prelim69Betty GallegosMexicoprelim
95prelim70David KreibichCzech Republicprelim
96prelim71Chen Zhao HongTaiwanprelim
97prelim72Kendrick HuSingaporeprelim
98prelim73Vu HoAustraliaprelim
99prelim74Terence WongHong Kongprelim
100prelim75Riccardo FraoliniItalyprelim
101prelim76Ginji MiuraJapanprelim wildcard
102prelim77Amane OkuboJapanprelim wildcard
103prelim78Andrew BergenUnited Statesprelim wildcard
104prelim79Marilyn LeungHong Kongprelim
106prelim81Salvatore CondelloAustraliaprelim
107prelim82Ni Bo WeiTaiwanprelim
108prelim83Muhammad ShaifuddinMalaysiaprelim
109prelim84Kaito TanakaJapanprelim wildcard
110prelim85Denny KoHong Kongprelim
111prelim86Thomas CaenFranceprelim
112prelim87Simpson Wong Wai SheukHong Kongprelim
113prelim88Azim JameelBruneiprelim
114prelim89Ryan LimMalaysiaprelim
115prelim90Shinji ToyodaJapanprelim wildcard
116prelim91J.M. OtazoSpainprelim
117prelim92Brad ForschingerAustraliaprelim
118prelim93Angus BeavisAustraliaprelim
wildcard1Toya KobayashiJapansemi-final prelim wildcard
wildcard2Benson FokHong Kongsemi-final prelim wildcard
wildcard3Izuru HasumiJapansemi-final prelim wildcard
wildcard4Andrew BergenUnited Statesprelim wildcard
wildcard5Yuki NishisakoJapanprelim wildcard
wildcard6Yuya YataniJapanprelim wildcard
wildcard7Colin BeckfordUnited Statesfinal semi-final prelim wildcard
wildcard8Ryota KomatsuJapanprelim wildcard
wildcard9Shinya KidoJapansemi-final prelim wildcard
wildcard10Hiroaki YoshiiJapanprelim wildcard
wildcard11Eric Tran-TonUnited Statessemi-final prelim wildcard
wildcard12Tatsuaki OkamotoJapanprelim wildcard
wildcard13Koyo HashimotoJapanprelim wildcard
wildcard14Clint ArmstrongUnited Statesprelim wildcard
wildcard15PiscoChinaprelim wildcard
wildcard16Ayumu HaradaJapansemi-final prelim wildcard
wildcard17Kevin NicholasUnited Statesprelim wildcard
wildcard18Daiki TanakaJapanprelim wildcard
wildcard19Kazuya MurataJapansemi-final prelim wildcard
wildcard20Tsukasa NambaJapansemi-final prelim wildcard
wildcard21Yuki ShigematsuJapanprelim wildcard
wildcard22Kento MuraokaJapansemi-final prelim wildcard
wildcard23Kaito TanakaJapanprelim wildcard
wildcard24Amane OkuboJapanprelim wildcard
wildcard25Weichuan WangChinasemi-final prelim wildcard
wildcard26Ginji MiuraJapanprelim wildcard
wildcard27Takumi SakamotoJapanprelim wildcard
wildcard28Ryosuke HaraJapanprelim wildcard
wildcard29Shinji ToyodaJapanprelim wildcard
wildcard30Kenta KushiroJapanprelim wildcard
wildcard31Tomoki ToyamaJapanprelim wildcard
wildcard32Lucas GremlerUnited Statesprelim wildcard
wildcard33Ryo IgarashiJapanprelim wildcard
119wildcard34Chen Hong DaChinawildcard
120wildcard35Vashek KroutilCzech Republicwildcard
121wildcard36Cai Zhi MingChinawildcard
122wildcard37Igor GalievRussiawildcard
123wildcard38Takahiro IizukaJapanwildcard
124wildcard39Yang Ze HuaChinawildcard
125wildcard40Hiromi TomiiJapanwildcard
126wildcard41Hirotaka AkibaJapanwildcard
127wildcard42Kento NodaJapanwildcard
128wildcard43Taro KomariJapanwildcard
129wildcard44Sitta NattasomboonThailandwildcard
130wildcard45Hiro IrifuneJapanwildcard
131wildcard46Kazuki MoriiJapanwildcard
132wildcard47Yoshitaka ToritaJapanwildcard
134wildcard49Toru MiyazakiJapanwildcard
135wildcard50Yuto ShishidoJapanwildcard
136wildcard51So TakaseJapanwildcard
137wildcard52Yohei KanabeJapanwildcard
138wildcard53Yoku KatoJapanwildcard
139wildcard54Eric KoloskiUnited Stateswildcard
140wildcard55Yuya YagiJapanwildcard
141wildcard56Nehemiah PetersonUnited Stateswildcard
142wildcard57Chingiz AlpyspayevKazakhstanwildcard
143wildcard58Tylor McCallumoreUnited Stateswildcard
144wildcard59Chan TimlokChinawildcard
145wildcard60Yugo NishimuraJapanwildcard
146wildcard61Chan Man FaiHong Kongwildcard
147wildcard62Jack YuAustraliawildcard
148wildcard63Shun MatsudaJapanwildcard
149wildcard64Matyas RacekCzech Republicwildcard
150wildcard65Tatsunari KadoJapanwildcard
151wildcard66Takayasu MurakamiJapanwildcard
152wildcard67Ryosuke IwasawaJapanwildcard
153wildcard68Hinata YamadaJapanwildcard
154wildcard69Aoi OguraJapanwildcard
155wildcard70Cory HendonUnited Stateswildcard
156wildcard71Yuya KudoJapanwildcard
157wildcard72Song Seung-HunRepublic of Koreawildcard
158wildcard73Reia ToritaJapanwildcard
159wildcard74Tsukuba TakahashiJapanwildcard
160wildcard75Ryo EnomotoJapanwildcard
161wildcard76Immran KhashMalaysiawildcard
162wildcard77Tsukasa RyuJapanwildcard
163wildcard78Kentato MannenJapanwildcard
164wildcard79Towa OhnoJapanwildcard
165wildcard80Yukihiro FujiwaraJapanwildcard
166wildcard81Yu IshiharaJapanwildcard
167wildcard82Tomoharu IsaiJapanwildcard
168wildcard83Hiroki AbeJapanwildcard
169wildcard84Shota SagaJapanwildcard
170wildcard85Masaki IidaJapanwildcard
171wildcard86Yuto FujiiJapanwildcard
172wildcard87Alec CampbellUnited Stateswildcard
173wildcard88Daichi TomiiJapanwildcard
174wildcard89Tomohiro HiratsukaJapanwildcard
175wildcard90Hiroki KatsumataJapanwildcard
176wildcard91Konosuke OkagawaJapanwildcard
177wildcard92Kyohei MatsumotoJapanwildcard
178wildcard93Hidemasa SembaJapanwildcard
179wildcard94Joji TakamatsuJapanwildcard
180wildcard95Ikumi KatoJapanwildcard
181wildcard96Yuki SuminoJapanwildcard
182wildcard97Ryosuke KawamuraJapanwildcard
183wildcard98Kohei SakatokuJapanwildcard
184wildcard99Yang Po ChunTaiwanwildcard
185wildcard100Yuki SakamotoJapanwildcard
186wildcard101Yuki TokunagaJapanwildcard
187wildcard102Daiju OkamuraJapanwildcard
188wildcard103Nick de ValpineUnited Stateswildcard
189wildcard104Daisuke SekiJapanwildcard
190wildcard105Hiroki IchikawaJapanwildcard
191wildcard106Im Yun-HanRepublic of Koreawildcard
192wildcard107Tomoaki DemizuJapanwildcard
193wildcard108Masato SasakiJapanwildcard
194wildcard109Ayoun KuoTaiwanwildcard
195wildcard110Shiqin DaiChinawildcard
196wildcard111Mimi ThianMalaysiawildcard
197wildcard112Chun WuThailandwildcard
198wildcard113Taisuke FukayaJapanwildcard
199wildcard114Chan Ka HoHong Kongwildcard
200wildcard115Yohei KawakamiJapanwildcard
201wildcard116Masashi KatoJapanwildcard
202wildcard117Daisuke NishiokaJapanwildcard
204wildcard119Ann ConnollyCzech Republicwildcard
205wildcard120He Jing HangChinawildcard
206wildcard121David WangChinawildcard
207wildcard122Jerry LiuChinawildcard
208wildcard123Im Chan-HyukRepublic of Koreawildcard
209wildcard124Eirik Saetre HoveNorwaywildcard
210wildcard125Junichi TadaJapanwildcard
211wildcard126Yang Yuan ChingTaiwanwildcard
212wildcard127Sean KangRepublic of Koreawildcard
213wildcard128Yusuke KikumaJapanwildcard
214wildcard129Tessa PiccilloUnited Stateswildcard
215wildcard130Jimmy HoTaiwanwildcard
216wildcard131Ittetsu HoritaJapanwildcard
217wildcard132Hans Wong-JensenSingaporewildcard
218wildcard133Chris MakitaPhilippineswildcard
219wildcard134Tomoaki ClarkUnited Stateswildcard
220wildcard135Connor ScholtenUnited Stateswildcard
221wildcard136Michael WangCanadawildcard
222wildcard137Kotoya TayamaJapanwildcard
223wildcard138Shen ChenweiChinawildcard
224wildcard139Shinya KishimotoJapanwildcard
225wildcard140Tokio KatsumataJapanwildcard
226wildcard141Tomoaki NakajimaJapanwildcard
227wildcard142Toya SakuraiJapanwildcard
228wildcard143Mathias DitlefsenNorwaywildcard
229wildcard144Peter YeungHong Kongwildcard
230wildcard145Kenshi MaedaJapanwildcard
231wildcard146Will GriffithsUnited Kingdomwildcard
232wildcard147Wen HaiYiChinawildcard
233wildcard148Takuji NomuraJapanwildcard
234wildcard149Shuichi ItoJapanwildcard
235wildcard150Christian NolascoUnited Stateswildcard
236wildcard151Michael ChangTaiwanwildcard
237wildcard152Kenji TakahashiJapanwildcard
238wildcard153Takumi KiyatakeJapanwildcard
240wildcard155Ryusuke KawanoJapanwildcard
241wildcard156Yasuhiro SakamotoJapanwildcard
242wildcard157Henry SongUnited Stateswildcard
243wildcard158Yuichiro MitsuiJapanwildcard
244wildcard159Brian MelfordUnited Stateswildcard
245wildcard160Hidefumi NakamuraJapanwildcard
246wildcard161Luis E AnacletoMexicowildcard
247wildcard162Takahiro YamadaJapanwildcard
248wildcard163Soichiro SugiyamaJapanwildcard
249wildcard164Nicholson Lam Ka HingHong Kongwildcard
250wildcard165Chang Wei LunTaiwanwildcard
251wildcard167Keita NashimotoJapanwildcard
252wildcard168Boming WangCanadawildcard
253wildcard169Tetsuya HiramatsuJapanwildcard

Wednesday, December 3, 2014

Vixie's metazones

From Vixie's 2005 paper "Federated Domain Name Service Using DNS Metazones". I couldn't find an implementation, and I've got a feeling the example zone is missing the prefix.

Script is at the bottom. Here's the example zone:

$TTL 3600

@ SOA ( 2005050704 3600 1800 604800 42 ) ;
@ NS
@ NS

masters         RT      10 ns-lah1.servers

allow-transfer  MG
                MG      ns-ext.

also-notify     RT      10 ns-ext.servers

ns-lah1 A
        AAAA    2001:4f8:2::9
ns-ext  A
        AAAA    2001:4f8:0:2::13

$ORIGIN         PTR        PTR        PTR

is to generate:

zone "" {
        type slave;
        file "sec/";
        masters {
        also-notify {
        allow-transfer {
                key ns-ext;

zone "" {
        type slave;
        file "sec/";
        masters {
        also-notify {
        allow-transfer {
                key ns-ext;

zone "" {
        type slave;
        file "sec/";
        masters {
        also-notify {
        allow-transfer {
                key ns-ext;


#!/usr/bin/env perl

# vim: set sts=2 sw=2 ts=8 et ai:

# 2014, Brad Forschinger

use strict;
use warnings;

use Net::DNS;

my $MZ_NAME = $ARGV[0] || "";

my $res = Net::DNS::Resolver->new;

my @mz = $res->axfr($MZ_NAME) or die "axfr: $!";

print make_zone_config(sort map { $_->ptrdname } grep { $_->type eq "PTR" } @mz);


sub make_zone_config {
  my $name = shift or return;

  "zone \"$name\" {\n",
  "\ttype slave;\n",
  "\tfile \"sec/$MZ_NAME/$name\";\n",
  conf_from_rt("masters",     $name),
  conf_from_rt("also-notify", $name),

sub conf_from_rt {
  my $statement = shift or return;

  "\t$statement {\n", (
    map {
      my $server = $_->intermediate;
      map { "\t\t" . $_->address . ";\n" }
      grep { $_->name eq $server && ($_->type eq "A" || $_->type eq "AAAA") } @mz;
    sort { $a->preference <=> $b->preference }
    grep { $_->type eq "RT" && $_->name =~ /^\Q$statement.\E/ } @mz

sub conf_transfer {
  "\tallow-transfer {\n", (
    map { "\t\tkey " . $_->mgmname . ";\n" }
    grep { $_->type eq "MG" && $_->name =~ /^allow-transfer\./ } @mz

Tuesday, August 12, 2014

Solaris 11.2 md5sums

188cbd0ac121c747ddab74135ef2935c  sol-11_2-ai-sparc.iso
537fe9cf222719aa16c0fa304605a844  sol-11_2-ai-sparc.usb
2bed667e94f5cb2a4b0e1b3667e08fc8  sol-11_2-openstack-sparc.uar
a15911df283e2988ffa237678ef7ad5b  sol-11_2-openstack-sparc.usb
af6f1d8aad4fe73b07a7e0accfd01914  sol-11_2-sparc.uar
f52486043c9b6405d948299995eaa743  sol-11_2-text-sparc.iso
998a4a57905a11a65d3a663a6e2805c0  sol-11_2-text-sparc.usb
2b3859bb7532cfe42214349dff9fcc23  sol-11_2-ai-x86.iso
462669f4ca48314a95ec98fb60aa952f  sol-11_2-ai-x86.usb
99a71c71bdbf7d9649fc2f24185a6934  sol-11_2-live-x86.iso
7817f06828b660fd1af8b9db22bef466  sol-11_2-live-x86.usb
75e3fc4d2b58c09d46511df27b4913cf  sol-11_2-openstack-x86.uar
c64a5b449c9f845704f85ed076306279  sol-11_2-openstack-x86.usb
c09f40ed91d43b0adf109c124154a2b4  sol-11_2-text-x86.iso
18cb289dcaa364af26ad2aab6c4b1e92  sol-11_2-text-x86.usb
135c78f5b9e459c9ece7ea3b14fddf97  sol-11_2-x86.uar
448619f56f48cd6dc7490ce379599f9a  sol-11_2-vbox.ova

Monday, January 20, 2014

generating a list of dates with sqlite3

By default there's a recursion limit of 1000.

pragma recursive_triggers = 1;                                                                                                                                 
create temp table dates (d text);                                                                                                                              
create temp trigger fill_dates after insert on dates                                                                                                           
    insert into dates (d)                                                                                                                                      
    select date(new.d, '+1 day') tomorrow                                                                                                                      
    where tomorrow < date(new.d, '+1 year', 'start of year');                                                                                                    
insert into dates (d) select date('now', 'start of year');                                                                                                      
select * from dates;