The code being posted (again with no comments or promise of correctness, sorry!), contains examples of problems associated with programming, mostly threading related, as you can see below. A basic description of each one:

• search.py – A simple implementation of a Basic Regular Expression (a Deterministic Finite State Machine) which should match a pattern and string
• webbot.py – A simple HTTP GET script which uses various authentication methods: Basic, Digest, Cookies, and SSL
• deadlock.py – A thread based example of the “deadlock” problem where 2 threads attempt to perform 2 related actions in reverse order of each other and obtain the locks in a staggered fashion such that they both are now waiting for each other to finish first before proceeding.
• Example: Thread1 wants to transfer money from Bob to Charlie & Thread2 wants to transfer money from Charlie to Bob. Thread1 first gets a lock on Bob’s account & Thread2 at the same time gets a lock on Charlie’s account. Now Thread1 is waiting to get a lock on Charlie’s account & Thread2 is waiting to get a lock on Bob’s account but they both can’t until one of them releases a lock.
• livelock.py – A thread based example of the “livelock” problem where 2 threads attempt to perform the same reversed action as above but instead attempt to release their own locks at the same time and then wait for the other to grab their lock for the same amount of time and then re-lock at the same time again causing an infinite loop to occur again.
• semaphore.py – The lock scenarios above are examples of binary “semaphores” so this is a thread based example of a counting “semaphore”. The implementation is an example where a library has 10 rooms to offer students, however, the front desk only keeps a count of the number of rooms free when a person enters or leaves a room. If no rooms are available, the thread is blocked and added to a simple First In First Out queue waiting for the room count to become positive again.
• monitor.py – This script is also based on the bank money transfer analogy as above except that it uses a real thread locking mechanism for both withdrawal and deposit actions to prevent both threads from performing different actions at the same time.
• mutex.py – This script demonstrates both an example of a problem and a “monitor” locking solution for when 2 threads attempt to remove adjacent items (i & i+1) in a Linked-List at the same time. Basically, Thread1 removing i will point i-1 at i+1 when Thread2 is trying to remove i+1 at the same time therefore allowing it to still exist afterwards.

search.py

#!/usr/bin/python
import os
import sys
def search(pattern, instr):
	allchars = []
	for x in range(0, 256):
		allchars.append(chr(x))
	# compile: [notflag, charset, numtimes, indexlist]
	# numtimes: {0:"0", 1:"1", ..., -1:"0 or 1", -2:"0 or more"}
	clist = []; clen = 0
	try:
		pidx = 0; plen = len(pattern)
		while (pidx < plen):
			pchar = pattern[pidx]
			if (pchar == "."):
				clist.append([0, allchars, 1, []]); clen += 1
			elif (pchar == "?"):
				clist[clen - 1][2] = -1
			elif (pchar == "*"):
				clist[clen - 1][2] = -2
			elif (pchar == "["):
				notflag = -1; charlist = []
				while (pidx < plen):
					pidx += 1; pchar = pattern[pidx]
					if ((notflag == -1) and (pchar == "^")):
						notflag = 1
					elif (pchar == "]"):
						break
					elif (pchar == "-"):
						for a in range(ord(pattern[pidx - 1]) + 1, ord(pattern[pidx + 1])):
							charlist.append(chr(a))
					else:
						charlist.append(pchar)
				if (notflag == -1):
					notflag = 0
				clist.append([notflag, charlist, 1, []]); clen += 1
			else:
				clist.append([0, [pchar], 1, []]); clen += 1
			pidx += 1
	except:
		return False
	#print(instr, pattern, clist)
	# search
	cidx = 0
	iidx = 0; ilen = len(instr)
	while ((cidx < clen) and (iidx < ilen)):
		#print(cidx,clist[cidx],iidx,instr[iidx])
		inchr = instr[iidx]
		match = (inchr in clist[cidx][1])
		if (clist[cidx][0] == 1):
			match = (not match)
		# match processing
		if (match):
			# if we matched
			# store this related input index and check the next input character (greedy)
			clist[cidx][3].append(iidx); iidx += 1
			if ((clist[cidx][2] == 1) or (clist[cidx][2] == -1)):
				# if this regex match count is ("1" OR "0 or 1") then try the next regex item for matches
				cidx += 1
		else:
			# if we did not match
			if ((clist[cidx][2] == -1) or (clist[cidx][2] == -2)):
				# if the regex match count is ("0 or 1" OR "0 or more") then try the next regex item for matches
				cidx += 1
			elif (len(clist[cidx][3]) > 0):
				# if this regex already has some matched input then try the next regex item for matches
				cidx += 1
			else:
				# last resort check to see if we can roll back to a past (greedy) regex match
				while (1):
					tidx = max(cidx - 1, 0)
					if (len(clist[tidx][3]) > 0):
						# if we found a past (greedy) regex match then use that past input index for this regex and check from there
						iidx = clist[tidx][3].pop()
						break
					cidx = tidx
					if (cidx < 1):
						# if we have gone back to the first regex then move the input index forward (search)
						iidx += 1
						break
	if (cidx >= clen):
		return True
	return False
def main():
	for line in sys.stdin.readlines():
		line = line.rstrip()
		if (search(sys.argv[1], line)):
			print(line)
if (__name__ == "__main__"):
	main()

webbot.py

#!/usr/bin/python

import base64
import hashlib
import os
import random
import ssl
import socket
import sys
import time

def parse_headers(httpresp):
	httphead = {}
	
	for httpline in httpresp.split("\n"):
		httpline = httpline.strip()
		if (not httpline):
			break
		headlist = httpline.split(":", 1)
		if (len(headlist) != 2):
			continue
		httphead[headlist[0].lower()] = headlist[1].strip()
	
	if ("www-authenticate" in httphead.keys()):
		httpauth = {}
		authlist = httphead["www-authenticate"].split(" ", 1)
		httpauth["type"] = authlist[0]
		flag = 0; keyn = ""; temp = ""
		for achr in authlist[1]:
			if (achr == '='):
				keyn = temp; temp = ""
				flag = 1
			elif ((achr == "'") or (achr == '"')):
				if (flag == 1):
					temp = ""
				if (flag == 2):
					httpauth[keyn] = temp; temp = ""
				flag += 1
			elif (achr == ','):
				if (temp != ""):
					httpauth[keyn] = temp; temp = ""
				flag = 3
			elif ((flag != 2) and (achr == ' ')):
				pass
			else:
				temp += achr
		if (temp != ""):
			httpauth[keyn] = temp; temp = ""
		httphead["www-auth"] = httpauth
	
	return httphead

def main():
	print("[Basic Auth]");print("")
	
	hostname = "httpbin.org"
	filename = "/basic-auth/baseuser/basepass"
	
	authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("baseuser:basepass")))
	cookie = ""
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	print(sockresp);print("");print(headlist)
	
	
	print("");print("")
	
	
	print("[Digest Auth]");print("")
	
	username = ("dig%duser%d" % (random.randint(1000, 9999), random.randint(1000, 9999)))
	password = ("dig%dpass%d" % (random.randint(1000, 9999), random.randint(1000, 9999)))
	hostname = "httpbin.org"
	filename = ("/digest-auth/auth/%s/%s" % (username, password))
	
	authhead = ""
	cookie = ""
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	nc = "00000001"; cn = "13377331"
	hao = hashlib.md5(username + ":" + headlist["www-auth"]["realm"] + ":" + password).hexdigest()
	hat = hashlib.md5("GET" + ":" + filename).hexdigest()
	har = hashlib.md5(hao + ":" + headlist["www-auth"]["nonce"] + ":" + nc + ":" + cn + ":" + "auth" + ":" + hat).hexdigest()
	
	authhead = ("Authorization: Digest username=\"%s\", realm=\"%s\", nonce=\"%s\", uri=\"%s\", qop=auth, nc=%s, cnonce=\"%s\", response=\"%s\", opaque=\"%s\"\r\n" % (username, headlist["www-auth"]["realm"], headlist["www-auth"]["nonce"], filename, nc, cn, har, headlist["www-auth"]["opaque"]))
	cookie = ("Cookie: %s\r\n" % (headlist["set-cookie"]))
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	print(sockresp);print("");print(headlist)
	
	
	print("");print("")
	
	
	print("[Cookie Auth]");print("")
	
	hostname = "www.httpwatch.com"
	filename = "/httpgallery/authentication/authenticatedimage/default.aspx"
	
	authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("httpwatch:abcd")))
	cookie = ""
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("httpwatch:efgh")))
	cookie = ("Cookie: %s\r\n" % (headlist["set-cookie"]))
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((hostname, 80))
	sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sockobjc.recv(1024)
	headlist = parse_headers(sockresp)
	
	print(sockresp);print("");print(headlist)
	
	
	print("");print("")
	
	
	print("[SSL Auth]");print("")
	
	hostname = "www.google.ca"
	filename = "/images/srpr/logo11w.png"
	
	authhead = ""
	cookie = ""
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sslsocko = ssl.wrap_socket(sockobjc)
	sslsocko.connect((hostname, 443))
	sslsocko.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
	sockresp = sslsocko.recv(1024)
	headlist = parse_headers(sockresp)
	
	print(sockresp);print("");print(headlist)

if (__name__ == "__main__"):
	main()

deadlock.py

#!/usr/bin/python

import os
import sys
import threading
import time

class Account:
	def __init__(self, amount):
		self.lock = 0
		self.exit = 0
		self.balance = amount
	
	def withdraw(self, amount):
		self.balance -= amount
	
	def deposit(self, amount):
		self.balance += amount
	
	def sync(self):
		while (self.lock == 1):
			if (self.exit == 1):
				print("deadlock exit triggered")
				sys.exit(0)
			time.sleep(0.5)
		self.lock = 1
		print("got lock on",self)
	
	def release(self):
		self.lock = 0
	
	def transfer(self, Accto, amount):
		self.sync()
		Accto.sync()
		
		self.withdraw(amount)
		Accto.deposit(amount)
		
		Accto.release()
		self.release()
	
	def show(self):
		return str(self.balance)

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.data = data
	
	def run(self):
		if (self.threadID == 1):
			src = "bob"; to = "charlie"
		if (self.threadID == 2):
			src = "charlie"; to = "bob"
		print("Before: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())
		print("Transfer: "+self.name+" from "+src+" to "+to); bank[src].transfer(bank[to], 5)
		print("After: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())

bank = {"bob":Account(100), "charlie":Account(200)}

thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)

thread1.start()
thread2.start()

time.sleep(3)
bank["bob"].exit = 1
bank["charlie"].exit = 1

livelock.py

#!/usr/bin/python

import os
import sys
import threading
import time

class Account:
	def __init__(self, amount):
		self.lock = 0
		self.exit = 0
		self.balance = amount
	
	def withdraw(self, amount):
		self.balance -= amount
	
	def deposit(self, amount):
		self.balance += amount
	
	def setlocks(self, linked):
		self.lock = 1
		waittime = 0.01
		print("setlocks started")
		while (1):
			if (linked.lock != 1):
				break
			if (self.exit == 1):
				print("livelock exit triggered")
				sys.exit(0)
			time.sleep(waittime)
			self.lock = 0
			time.sleep(waittime)
			self.lock = 1
			time.sleep(waittime)
		linked.lock = 1
	
	def dellocks(self, linked):
		linked.lock = 0
		self.lock = 0
	
	def transfer(self, Accto, amount):
		self.setlocks(Accto)
		
		self.withdraw(amount)
		Accto.deposit(amount)
		
		self.dellocks(Accto)
	
	def show(self):
		return str(self.balance)

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.data = data
	
	def run(self):
		if (self.threadID == 1):
			src = "bob"; to = "charlie"
		if (self.threadID == 2):
			src = "charlie"; to = "bob"
		print("Before: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())
		print("Transfer: "+self.name+" from "+src+" to "+to); bank[src].transfer(bank[to], 5)
		print("After: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())

bank = {"bob":Account(100), "charlie":Account(200)}

thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)

thread1.start()
thread2.start()

time.sleep(3)
bank["bob"].exit = 1
bank["charlie"].exit = 1

semaphore.py

#!/usr/bin/python

import os
import random
import sys
import threading
import time

class Library:
	def __init__(self):
		self.rooms = ([None]*10)
		self.numb = 10
		self.queue = []
	
	def wait(self, caller):
		self.queue.append(caller)
		while ((self.numb < 1) or (self.queue[0] != caller)):
			time.sleep(0.1)
		self.numb -= 1
		for x in range(0, 10):
			if (self.rooms[x] == None):
				self.rooms[x] = caller
				self.queue.pop(0)
				return x
		sys.stderr.write("ERROR: wait() - Could not find a room!\n")
		sys.exit(1)
		return -1
	
	def signal(self, caller):
		for x in range(0, 10):
			if (self.rooms[x] == caller):
				self.rooms[x] = None
				self.numb += 1
				return x
		sys.stderr.write("ERROR: signal() - Could not find our room!\n")
		sys.exit(1)
		return -1
	
	def show(self):
		return self.numb
	
	def disp(self):
		o = ""
		o += ("rooms / time:%d\n" % (int(time.time())))
		for x in range(0, 10):
			if (self.rooms[x] == None):
				o += ("room[%d]=None\n" % (x))
			else:
				o += ("room[%d]=%s/%d\n" % (x, self.rooms[x].name, self.rooms[x].init + self.rooms[x].secs))
		o += ("\n")
		o += ("num[%d] / queue[%d] = " % (self.numb, len(self.queue)))
		for item in self.queue:
			o += ("%s, " % (item.name))
		o += ("\n")
		sys.stdout.write(("\n"*50) + o.strip() + "\n\n")

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.library = data
	
	def run(self):
		self.init = int(time.time())
		self.secs = random.randint(1, 9)
		room = self.library.wait(self)
		time.sleep(self.secs)
		left = self.library.signal(self)
		sys.exit(0)

x = 0
study = Library()
while (1):
	thread = myThread(x, "Thread-%d" % (x), study)
	thread.start()
	secs = 0.5
	study.disp()
	time.sleep(secs)
	x += 1

monitor.py

#!/usr/bin/python

import os
import sys
import threading
import time

class Account:
	def __init__(self, amount, iden):
		self.balance = amount
		self.name = iden
	
	def withdraw(self, amount):
		threadLock.acquire()
		print(time.ctime(time.time())+" withdraw "+" from "+self.name+" : "+str(self.balance)+" - "+str(amount)+" = "+str(self.balance-amount))
		if (self.balance >= amount):
			self.balance -= amount
		threadLock.release()
	
	def deposit(self, amount):
		threadLock.acquire()
		print(time.ctime(time.time())+" deposit "+" to "+self.name+" : "+str(self.balance)+" + "+str(amount)+" = "+str(self.balance+amount))
		if (amount > 0):
			self.balance += amount
		threadLock.release()
	
	def show(self):
		return str(self.balance)

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.data = data
	
	def run(self):
		#threadLock.acquire()
		if (self.threadID == 1):
			src = "bob"; to = "charlie"
		if (self.threadID == 2):
			src = "charlie"; to = "bob"
		for x in range(0, 3):
			bank[src].withdraw(5 * self.threadID)
			bank[to].deposit(5 * self.threadID)
			time.sleep(self.threadID)
		#threadLock.release()

threadLock = threading.Lock()
threads = []
bank = {"bob":Account(100, "bob"), "charlie":Account(200, "charlie")}

thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)

thread1.start()
thread2.start()

threads.append(thread1)
threads.append(thread2)

for t in threads:
	t.join()

mutex.py

#!/usr/bin/python

import os
import sys
import threading
import time

class LinkedList:
	def __init__(self, data):
		self.data = data
		self.next = None
	
	def getnext(self):
		return self.next
	
	def setnext(self, next):
		self.next = next
	
	def getdata(self):
		return self.data
	
	def add(self, data):
		temp = self
		while (temp.next != None):
			temp = temp.next
		temp.next = LinkedList(data)
	
	def get(self):
		o = []
		temp = self
		while (1):
			o.append(temp)
			if (temp.next == None):
				break
			temp = temp.next
		return o

class myThread(threading.Thread):
	def __init__(self, threadID, name, data):
		threading.Thread.__init__(self)
		self.threadID = threadID
		self.name = name
		self.person = data
	
	def run(self):
		if (self.threadID > 1):
			threadLock.acquire()
		if ((self.threadID % 2) == 0):
			i = (len(self.person) - 1 - 4)
		if ((self.threadID % 2) == 1):
			i = (len(self.person) - 1 - 3)
		self.person[i-1].next = self.person[i+1]
		time.sleep(0.1)
		self.person.pop(i)
		if (self.threadID > 1):
			threadLock.release()

threadLock = threading.Lock()
threads = []
person = LinkedList("Bob")
person.add("Charlie")
person.add("Dave")
person.add("Earl")
person.add("Frank")
person.add("George")
person.add("Hal")
person.add("Ian")
person.add("Jon")

print("")
l = person.get()
for i in l:
	print(i.data)
print("")

print("Deleting "+l[len(l) - 1 - 4].data+" and "+l[len(l) - 1 - 3].data+" without threadlock")

thread0 = myThread(0, "Thread-0", l)
thread1 = myThread(1, "Thread-1", l)

thread0.start()
thread1.start()

threads.append(thread0)
threads.append(thread1)

for t in threads:
	t.join()

print("")
l = person.get()
for i in l:
	print(i.data)
print("")

print("Deleting "+l[len(l) - 1 - 4].data+" and "+l[len(l) - 1 - 3].data+" with threadlock")

thread2 = myThread(2, "Thread-0", l)
thread3 = myThread(3, "Thread-1", l)

thread2.start()
thread3.start()

threads.append(thread2)
threads.append(thread3)

for t in threads:
	t.join()

print("")
l = person.get()
for i in l:
	print(i.data)
print("")

The code is just a basic, rough implementation of this stuff in case anyone is interested in studying the theory of how they work below (no comments or good variable names included, sorry…). It covers a: Merge sort, Quick sort, Radix (LSD) sort, Binary search, Linked-List hash table, & Pipe/Fork-Word-Counting map reduce (in Python & C).

Running sorts.py

('key-hash', 'jonnjonn', '->', '0x8bb05860')
('key-value:', 'jonnjonn', '=', {'home': '/home/jonnjonn', 'gid': 4, 'uid': 4, 'name': 'Jon Chipps'})
('key-value:', 'jonnjonn', '=', {'home': '/home/_jonnjonn_', 'gid': 4, 'uid': 4, 'name': 'Jon Chipps'})

('key-hash', 'jonnjono', '->', '0xf4c7560')
('key-value:', 'jonnjono', '=', {'home': '/home/jonnjono', 'gid': 5, 'uid': 5, 'name': 'Jon Chipps'})
('key-value:', 'jonnjono', '=', {'home': '/home/_jonnjono_', 'gid': 5, 'uid': 5, 'name': 'Jon Chipps'})

('key-hash', 'jonxjonp', '->', '0x2494c160')
('key-value:', 'jonxjonp', '=', {'home': '/home/jonxjonp', 'gid': 6, 'uid': 6, 'name': 'Jon Chipps'})
('key-value:', 'jonxjonp', '=', {'home': '/home/_jonxjonp_', 'gid': 6, 'uid': 6, 'name': 'Jon Chipps'})

('key-hash', 'jonpjonx', '->', '0xe346c4e0')
('key-value:', 'jonpjonx', '=', {'home': '/home/jonpjonx', 'gid': 7, 'uid': 7, 'name': 'Jon Chipps'})
('key-value:', 'jonpjonx', '=', {'home': '/home/_jonpjonx_', 'gid': 7, 'uid': 7, 'name': 'Jon Chipps'})

('map-reduce', 'search', ['better', 8])

Sorting...
('merge_r:', 262145, 'items', 'took', 1.4660530090332031, 'seconds', '385a7adb')
('quick_r:', 262145, 'items', 'took', 1.087796926498413, 'seconds', '385a7adb')
('radixlsd_f:', 262145, 'items', 'took', 1.1461758613586426, 'seconds', '385a7adb')
Searching...
('bin_search_r:', True, 'index', 1368, '=', 51966, 'took', 2.5033950805664062e-05, 'seconds')

Running ./sorts 2> /dev/null

key-hash:jonnjonn=0x8bb05860
look:22624/-1/jonnjonn:(nil)/(nil)/(nil)
look:22624/0/jonnjonn:0x20c2060/0x20c2010/(nil)
jonnjonn={uid:jonnjonn, name:Jon Chipps, uid:1, gid:1, home:/home/jonnjonn}
look:22624/0/jonnjonn:0x20c2060/0x20c2010/(nil)
look:22624/0/jonnjonn:0x20c2060/0x20c2080/(nil)
jonnjonn={uid:jonnjonn, name:Jon Chipps, uid:1, gid:1, home:/home/_jonnjonn_}

key-hash:jonnjono=0xf4c7560
look:30048/-1/jonnjono:(nil)/(nil)/(nil)
look:30048/0/jonnjono:0x20c20d0/0x20c2010/(nil)
jonnjono={uid:jonnjono, name:Jon Chipps, uid:2, gid:2, home:/home/jonnjono}
look:30048/0/jonnjono:0x20c20d0/0x20c2010/(nil)
look:30048/0/jonnjono:0x20c20d0/0x20c20f0/(nil)
jonnjono={uid:jonnjono, name:Jon Chipps, uid:2, gid:2, home:/home/_jonnjono_}

key-hash:jonxjonp=0x2494c160
look:49504/-1/jonxjonp:(nil)/(nil)/(nil)
look:49504/0/jonxjonp:0x20c2140/0x20c2010/(nil)
jonxjonp={uid:jonxjonp, name:Jon Chipps, uid:3, gid:3, home:/home/jonxjonp}
look:49504/0/jonxjonp:0x20c2140/0x20c2010/(nil)
look:49504/0/jonxjonp:0x20c2140/0x20c2160/(nil)
jonxjonp={uid:jonxjonp, name:Jon Chipps, uid:3, gid:3, home:/home/_jonxjonp_}

key-hash:jonpjonx=0xe346c4e0
look:50400/-1/jonpjonx:(nil)/(nil)/(nil)
look:50400/0/jonpjonx:0x20c21b0/0x20c2010/(nil)
jonpjonx={uid:jonpjonx, name:Jon Chipps, uid:4, gid:4, home:/home/jonpjonx}
look:50400/0/jonpjonx:0x20c21b0/0x20c2010/(nil)
look:50400/0/jonpjonx:0x20c21b0/0x20c21d0/(nil)
jonpjonx={uid:jonpjonx, name:Jon Chipps, uid:4, gid:4, home:/home/_jonpjonx_}

merge-r:70/ms
quick-r:40/ms
radixlsd-r:30/ms
binsearch-r[13455]=51966

mapreduce-search('better'):8

–code–

sorts.py

#!/usr/bin/python

import hashlib
import os
import random
import re
import select
import sys
import time

def merge_r(list):
	m = len(list)
	if (m < 2):
		return list
	q = (m / 2)
	l = list[0:q]
	r = list[q:m]
	n = (m - q)
	# recursive call on half-split lists
	l = merge_r(l)
	r = merge_r(r)
	# merge sort core loop
	i = 0; li = 0; ri = 0
	while (i < m):
		if ((li < q) and (ri < n)):
			if (l[li] < r[ri]):
				list[i] = l[li]; i += 1; li += 1
			else:
				list[i] = r[ri]; i += 1; ri += 1
		else:
			if (li >= q):
				while (ri < n):
					list[i] = r[ri]; i += 1; ri += 1
			if (ri >= n):
				while (li < q):
					list[i] = l[li]; i += 1; li += 1
	return list

def quick_r(list):
	llen = len(list)
	if (llen < 2):
		return list
	lptr = 0; pivp = (llen / 2); rptr = (llen - 1)
	pivv = list[pivp]
	# search for any left & right values to swap around our pivot point
	while (1):
		if (lptr > rptr):
			break
		# ignore any left & right values which are already in place
		while (list[lptr] < pivv):
			lptr += 1
		while (list[rptr] > pivv):
			rptr -= 1
		# perform a left & right swap if the left index is less than the right index
		if (lptr <= rptr):
			temp = list[lptr]; list[lptr] = list[rptr]; list[rptr] = temp
			lptr += 1; rptr -= 1
	# note: at this point the left & right pointers should have crossed each other
	# recursive call on the left-half list
	l = quick_r(list[0:rptr+1])
	# save any middle items that are not being processed any further
	m = []
	if ((lptr - rptr) > 1):
		m = list[rptr+1:lptr]
	# recursive call on the right-half list
	r = quick_r(list[lptr:llen])
	return (l + m + r)

def radixlsd_f(list):
	llen = len(list)
	if (llen < 2):
		return list
	i = 0; m = 1
	while (i < m):
		# create buckets for decimal digits 0-9
		buckets = (10*[None])
		x = 0
		while (x < llen):
			# find the longest decimal integer during the first round
			if (i == 0):
				temp = abs(list[x]); d = 1
				while (temp > 0):
					temp = (temp / 10)
					d += 1
				m = max(m, d)
			# place the integer in its related bucket for this round
			b = ((list[x] / (10 ** i)) % 10)
			if (buckets[b] == None):
				buckets[b] = []
			buckets[b].append(list[x])
			x += 1
		# assign the bucket lists back into the main list to be sorted again
		blist = []
		for k in range(0, 10):
			if (buckets[k] != None):
				blist.extend(buckets[k])
		#print(list,buckets[0:10],blist)
		list = blist
		i += 1
	return list

def bin_search_r(list, item, lo=None, hi=None):
	if ((lo == None) or (hi == None)):
		lo = 0
		hi = len(list)
	mid = ((hi - lo) / 2)
	#print(lo,mid,hi,list[lo+mid])
	if (list[lo + mid] == item):
		return (lo + mid)
	if ((hi - lo) < 1):
		return -1
	if (list[lo + mid] < item):
		return bin_search_r(list, item, lo=lo+mid+1, hi=hi)
	return bin_search_r(list, item, lo=lo, hi=hi-mid-1)

class HashTable:
	def __init__(self):
		self.size = (2**16)
		self.data = ([[]]*self.size)
	
	def hash(self, data):
		i = 0; l = len(data); j = 0
		p = 0; z = l; h = 0
		while ((j < l) or (j < 256)):
			c = ord(data[i])
			s = (24 - ((j % 4) * 8))
			p = (p | (c << s))
			if (s == 0):
				#print("hash",hex(h),"^",hex(p),"^",hex(z))
				h = (h ^ (p ^ z))
				p = 0
			z = (((z+(c+j)) + (z^(c^j)) + (z*(c*j)) + (z&(c&j))) & 0xffffffff)
			i = ((i + 1) % l)
			j = (j + 1)
		if (p != 0):
			#print("hash",hex(h),"^",hex(p),"^",hex(z))
			h = (h ^ (p ^ z))
		return h
	
	def look(self, k):
		i = (self.hash(k) % self.size)
		j = -1
		for e in self.data[i]:
			if (e[0] == k):
				j = ((j + 1) * -1)
				break
			j -= 1
		return [i, j]
	
	def g(self, k):
		k = str(k)
		z = self.look(k)
		i = z[0]; j = z[1]
		#print("get",i,j)
		try:
			return self.data[i][j][1]
		except:
			return None
	
	def s(self, k, v):
		k = str(k)
		z = self.look(k)
		i = z[0]; j = z[1]
		#print("set",i,j)
		if (j < 0):
			self.data[i].append([k, v])
		else:
			self.data[i][j][1] = v

class MapReduce:
	def __init__(self):
		self.pids = []
	
	def map(self):
		self.pids = []
		self.data = []
		for x in range(0, 3):
			(r, w) = os.pipe()
			p = os.fork()
			if (p == 0):
				os.close(r)
				w = os.fdopen(w, "w")
				f = open("/tmp/textfile%d.txt" % (x), "r")
				d = f.read().lower().replace("\r", " ").replace("\n", " ")
				d = re.sub("[^a-z]+", " ", d)
				d = re.sub(" [ ]+", " ", d)
				l = d.split(" ")
				f.close()
				m = {}
				for n in l:
					if (not n):
						continue
					if (not n in m.keys()):
						m[n] = 0
					m[n] += 1
				g = {}
				for k in m.keys():
					if (not m[k] in g.keys()):
						g[m[k]] = []
					g[m[k]].append(k)
				l = g.keys()
				l = sorted(l)
				for k in l:
					w.write("%d %s\n" % (k, " ".join(g[k])))
				w.close()
				sys.exit(0)
			else:
				os.close(w)
				r = os.fdopen(r, "r")
				self.pids.append([p, r, "", 0])
		while (1):
			inplist = []
			for c in self.pids:
				if (c[3] == 0):
					inplist.append(c[1])
			if (len(inplist) < 1):
				break
			(inpready, outready, errready) = select.select(inplist, [], [])
			for s in inpready:
				for c in self.pids:
					if (c[1] == s):
						d = c[1].read()
						if (not d):
							c[3] = 1
						else:
							c[2] += d
		for c in self.pids:
			os.wait()
		for c in self.pids:
			for l in c[2].split("\n"):
				self.data.append(l)
	
	def reduce(self):
		self.count = {}
		for l in self.data:
			if (l.strip() == ""):
				continue
			m = l.split(" ")
			n = int(m[0])
			for w in m[1:]:
				if (not w in self.count.keys()):
					self.count[w] = 0
				self.count[w] += n
	
	def search(self, word):
		try:
			return [word, self.count[word]]
		except:
			return [word, 0]

def main():
	print("")
	
	ht = HashTable()
	i = 4
	for k in ["jonnjonn", "jonnjono", "jonxjonp", "jonpjonx"]:
		print("key-hash",k,"->",hex(ht.hash(str(k))))
		ht.s(k, {"uid":k,"name":"Jon Chipps","uid":i,"gid":i,"home":"/home/%s"%(k)})
		print("key-value:",k,"=",ht.g(k))
		ht.s(k, {"uid":k,"name":"Jon Chipps","uid":i,"gid":i,"home":"/home/_%s_"%(k)})
		print("key-value:",k,"=",ht.g(k))
		print("")
		i += 1
	
	mr = MapReduce()
	mr.map()
	mr.reduce()
	print("map-reduce","search",mr.search("better"))
	
	print("")
	
	numa = []; numb = []; numc = []
	#sys.stderr.write(str(2**18)+"\n")
	for x in range(0, 2**18):
		r = int(random.random() * (10**7))
		numa.append(r); numb.append(r); numc.append(r)
		#sys.stderr.write(str(r)+"\n")
	numa.append(51966); numb.append(51966); numc.append(51966)
	print("Sorting...")
	a=time.time();m=merge_r(numa);b=time.time();h=hashlib.md5(str(m)).hexdigest();print("merge_r:",len(m),"items","took",b-a,"seconds",h[0:8])
	a=time.time();q=quick_r(numb);b=time.time();i=hashlib.md5(str(q)).hexdigest();print("quick_r:",len(q),"items","took",b-a,"seconds",i[0:8])
	a=time.time();r=radixlsd_f(numc);b=time.time();j=hashlib.md5(str(r)).hexdigest();print("radixlsd_f:",len(r),"items","took",b-a,"seconds",j[0:8])
	if ((h != i) or (i != j)):
		for x in range(0, 2**18):
			sys.stderr.write(str(m[x])+" "+str(q[x])+" "+str(r[x])+"\n")
		sys.exit(0)
	print("Searching...")
	a=time.time();k=bin_search_r(m, 51966);b=time.time();print("bin_search_r:",51966 in m,"index",k,"=",m[k],"took",b-a,"seconds")
	
	print("")

if (__name__ == "__main__"):
	main()

mr.c

char **mr_data = NULL;
int mr_llen = 0;
char **mr_words = NULL;
int *mr_counts = NULL;

int mr_index(char **list, int size, char *item)
{
	int x;
	for (x = 0; x < size; ++x)
	{
		if (strcmp(list[x], item) == 0)
		{
			return x;
		}
	}
	return -1;
}

void mr_lower(char *word)
{
	while (*word != '\0')
	{
		*word = (*word | 0x60);
		++word;
	}
}

char *mr_word(char *word)
{
	int x;
	char *c = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
	char *a = NULL, *b = NULL;
	while ((a == NULL) || (b == NULL))
	{
		if (*word == '\0') { break; }
		if (a == NULL)
		{
			int f = 0;
			for (x = 0; x < 52; ++x)
			{
				if (*word == c[x]) { f = 1; }
			}
			if (f == 1) { a = word; }
		}
		else if (b == NULL)
		{
			int f = 0;
			for (x = 0; x < 52; ++x)
			{
				if (*word == c[x]) { f = 1; }
			}
			if (f == 0) { b = word; }
		}
		++word;
	}
	if (b != NULL) { *b = '\0'; }
	return a;
}

void mr_map()
{
	int x, y, z;
	long size;
	char filename[1024];
	int rw[3][2];
	char *data = NULL;
	int cmax = 1;
	
	mr_llen = 0;
	mr_words = NULL;
	mr_counts = NULL;
	
	for (x = 0; x < 3; ++x)
	{
		pipe(rw[x]);
		pid_t p = fork();
		if (p == 0)
		{
			close(rw[x][0]);
			
			bzero(filename, 1020 * sizeof(char));
			snprintf(filename, 1010, "/tmp/textfile%d.txt", x);
			FILE *f = fopen(filename, "r");
			
			fseek(f, 0, SEEK_END);
			size = ftell(f);
			fseek(f, 0, SEEK_SET);
			
			data = malloc((size + 24) * sizeof(char));
			bzero(data, (size + 20) * sizeof(char));
			fread(data, size + 10, sizeof(char), f);
			fclose(f);
			
			char *w = data;
			while ((w = mr_word(w)) != NULL)
			{
				mr_lower(w);
				//printf("[%d] (%s)\n", x, w);
				int i = mr_index(mr_words, mr_llen, w);
				if (i < 0)
				{
					mr_llen = (mr_llen + 1);
					mr_words = realloc(mr_words, mr_llen * sizeof(char *));
					mr_counts = realloc(mr_counts, mr_llen * sizeof(int));
					i = (mr_llen - 1);
					mr_words[i] = strdup(w);
					mr_counts[i] = 0;
				}
				mr_counts[i] += 1;
				cmax = max(cmax, mr_counts[i]);
				w += (strlen(w) + 1);
			}
			
			write(rw[x][1], &size, 1 * sizeof(long));
			
			for (y = 1; y <= cmax; ++y)
			{
				int f = 0;
				bzero(data, (size + 20) * sizeof(char));
				snprintf(data, (size + 10) * sizeof(char), "%d", y);
				for (z = 0; z < mr_llen; ++z)
				{
					if (mr_counts[z] == y)
					{
						strncat(data, " ", size + 10 - strlen(data));
						strncat(data, mr_words[z], size + 10 - strlen(data));
						free(mr_words[z]);
						f = 1;
					}
				}
				strncat(data, "\n", size + 10 - strlen(data));
				if (f == 1) { write(rw[x][1], data, strlen(data)); }
			}
			
			close(rw[x][1]);
			free(data);
			free(mr_counts);
			free(mr_words);
			exit(0);
		}
		else
		{
			close(rw[x][1]);
		}
	}
	
	mr_data = malloc(3 * sizeof(char *));
	for (x = 0; x < 3; ++x)
	{
		read(rw[x][0], &size, 1 * sizeof(long));
		mr_data[x] = malloc((size + 24) * sizeof(char));
		bzero(mr_data[x], (size + 20) * sizeof(char));
		char *w = mr_data[x];
		while (1)
		{
			mr_llen = read(rw[x][0], w, size + 10 - strlen(mr_data[x]));
			if (mr_llen < 1) { break; }
			w += mr_llen;
		}
		//printf("%s\n",mr_data[x]);
		close(rw[x][0]);
		wait(NULL);
	}
}

void mr_reduce()
{
	int x;
	
	mr_llen = 0;
	mr_words = NULL;
	mr_counts = NULL;
	
	for (x = 0; x < 3; ++x)
	{
		char *w = mr_data[x], *p, *q;
		int c = 0, f = 0;
		while (*w != '\0')
		{
			if (*w == '\n') { c = 0; f = 0; ++w; continue; }
			if (*w == ' ') { f += 1; ++w; continue; }
			if (f == 0) { c = ((c * 10) + (*w - '0')); ++w; continue; }
			else
			{
				p = strchr(w, ' ');
				q = strchr(w, '\n');
				if (p == NULL) { p = q; }
				else if (q != NULL) { if (q < p) { p = q; } }
				if (p != NULL)
				{
					char t = *p;
					*p = '\0';
					
					//printf("mr-add[%d]+=(%s:%d)\n", x, w, c);
					
					int i = mr_index(mr_words, mr_llen, w);
					if (i < 0)
					{
						mr_llen = (mr_llen + 1);
						mr_words = realloc(mr_words, mr_llen * sizeof(char *));
						mr_counts = realloc(mr_counts, mr_llen * sizeof(int));
						i = (mr_llen - 1);
						mr_words[i] = strdup(w);
						mr_counts[i] = 0;
					}
					mr_counts[i] += c;
					
					*p = t;
					w = p;
					continue;
				}
			}
		}
	}
}

int mr_search(char *word)
{
	int i = mr_index(mr_words, mr_llen, word);
	if (i > -1)
	{
		return mr_counts[i];
	}
	return -1;
}

ht.c

#define ht_size 65536
struct ht_data_s { char *k; void *v; struct ht_data_s *n; };
typedef struct ht_data_s ht_data_t;
ht_data_t ht_data[ht_size];
int ht_stat = 0;

unsigned long ht_hash(char *data)
{
	unsigned long i = 0, l = strlen(data), j = 0;
	unsigned long p = 0, z = l, h = 0;
	while ((j < l) || (j < 256))
	{
		unsigned int c = data[i];
		unsigned int s = (24 - ((j % 4) * 8));
		p = (p | (c << s));
		if (s == 0)
		{
			h = (h ^ (p ^ z));
			p = 0;
		}
		z = (((z+(c+j)) + (z^(c^j)) + (z*(c*j)) + (z&(c&j))) & 0xffffffff);
		i = ((i + 1) % l);
		j = (j + 1);
	}
	if (p != 0)
	{
		h = (h ^ (p ^ z));
	}
	return h;
}

ht_data_t *ht_look(unsigned long *i, long *j, char *k)
{
	if (ht_stat == 0)
	{
		bzero(ht_data, ht_size * sizeof(ht_data_t));
		ht_stat = 1;
	}
	*i = (ht_hash(k) % ht_size);
	*j = -1;
	ht_data_t *ht_item = &(ht_data[*i]);
	while ((*ht_item).k != NULL)
	{
		if (strcmp((*ht_item).k, k) == 0)
		{
			*j = (((*j) + 1) * -1);
			break;
		}
		*j = ((*j) - 1);
		if ((*ht_item).n == NULL)
		{
			break;
		}
		ht_item = (*ht_item).n;
	}
	printf("look:%lu/%ld/%s:%p/%p/%p\n", *i, *j, k, (*ht_item).k, (*ht_item).v, (*ht_item).n);
	return ht_item;
}

void *ht_g(char *k)
{
	unsigned long i; long j;
	ht_data_t *ht_item = ht_look(&i, &j, k);
	return (*ht_item).v;
}

void ht_s(char *k, void *v)
{
	unsigned long i; long j;
	ht_data_t *ht_item = ht_look(&i, &j, k);
	if (j < 0)
	{
		if ((*ht_item).k == NULL)
		{
			(*ht_item).k = strdup(k);
			(*ht_item).v = v;
			(*ht_item).n = NULL;
		}
		else
		{
			ht_data_t *ht_temp = malloc(1 * sizeof(ht_data_t));
			(*ht_temp).k = strdup(k);
			(*ht_temp).v = v;
			(*ht_temp).n = NULL;
			(*ht_item).n = ht_temp;
		}
	}
	else
	{
		if ((*ht_item).v != NULL)
		{
			free((*ht_item).v);
		}
		(*ht_item).v = v;
	}
}

sorts.c

//gcc -Wall -o3 -lm -o sorts sorts.c

int max(a, b) { if (a < b) { return b; } return a; }

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <time.h>
#include <unistd.h>

#include <sys/types.h>
#include <sys/wait.h>

#include "ht.c"
#include "mr.c"

int merge_r(int *list, int size)
{
	if (size < 2) { return 0; }
	int a[size];
	bcopy(list, a, size * sizeof(int));
	int q = (size / 2);
	int n = (size - q);
	int *l = a;
	int *r = (a + q);
	merge_r(l, q);
	merge_r(r, n);
	int i = 0, li = 0, ri = 0;
	while (i < size)
	{
		if ((li < q) && (ri < n))
		{
			if (l[li] < r[ri]) { list[i] = l[li]; i += 1; li += 1; }
			else { list[i] = r[ri]; i += 1; ri += 1; }
		}
		else
		{
			if (li >= q)
			{
				while (ri < n) { list[i] = r[ri]; i += 1; ri += 1; }
			}
			if (ri >= n)
			{
				while (li < q) { list[i] = l[li]; i += 1; li += 1; }
			}
		}
	}
	return 0;
}

int quick_r(int *list, int size)
{
	if (size < 2) { return 0; }
	int lptr = 0, pivp = (size / 2), rptr = (size - 1);
	int pivv = list[pivp];
	while (1)
	{
		if (lptr > rptr) { break; }
		while (list[lptr] < pivv) { lptr += 1; }
		while (list[rptr] > pivv) { rptr -= 1; }
		if (lptr <= rptr)
		{
			int temp = list[lptr]; list[lptr] = list[rptr]; list[rptr] = temp;
			lptr += 1; rptr -= 1;
		}
	}
	quick_r(list, rptr + 1);
	quick_r(list + lptr, size - lptr);
	return 0;
}

int radixlsd_f(int *list, int size)
{
	int i = 0, m = 1;
	int lengths[10], sizes[10];
	int **buckets = malloc(10 * sizeof(int *));
	int x, y, z;
	int d, b, p;
	bzero(sizes, 10 * sizeof(int));
	for (y = 0; y < 10; ++y) { buckets[y] = NULL; }
	while (i < m)
	{
		bzero(lengths, 10 * sizeof(int));
		x = 0; p = pow(10, i);
		while (x < size)
		{
			if ((i == 0) && (abs(list[x]) > m))
			{
				m = list[x];
			}
			b = ((list[x] / p) % 10);
			lengths[b] += 1;
			if (lengths[b] > sizes[b])
			{
				sizes[b] += 10;
				buckets[b] = realloc(buckets[b], sizes[b] * sizeof(int));
			}
			buckets[b][lengths[b] - 1] = list[x];
			x += 1;
		}
		x = 0;
		for (y = 0; y < 10; ++y)
		{
			for (z = 0; z < lengths[y]; ++z)
			{
				list[x] = buckets[y][z]; x += 1;
			}
		}
		if (i == 0)
		{
			d = 0;
			while (m != 0)
			{
				m = (m / 10);
				d += 1;
			}
			m = d;
		}
		i += 1;
	}
	return 0;
}

int bin_search_rp(int *list, int item, int lo, int hi)
{
	int mid = ((hi - lo) / 2);
	//print(lo,mid,hi,list[lo+mid])
	if (list[lo + mid] == item)
	{
		return (lo + mid);
	}
	if ((hi - lo) < 1)
	{
		return -1;
	}
	if (list[lo + mid] < item)
	{
		return bin_search_rp(list, item, lo+mid+1, hi);
	}
	return bin_search_rp(list, item, lo, hi-mid-1);
}

int bin_search_r(int *list, int size, int item)
{
	return bin_search_rp(list, item, 0, size);
}

int main(int argc, char **argv)
{
	printf("\n");
	
	int i = 0;
	char *keys[4] = { "jonnjonn", "jonnjono", "jonxjonp", "jonpjonx" };
	char temp[1028];
	for (i = 0; i < 4; ++i)
	{
		printf("key-hash:%s=0x%lx\n", keys[i], ht_hash(keys[i]));
		
		bzero(temp, 1028 * sizeof(char));
		snprintf(temp, 1024, "{uid:%s, name:Jon Chipps, uid:%d, gid:%d, home:/home/%s}", keys[i], i + 1, i + 1, keys[i]);
		ht_s(keys[i], strdup(temp));
		printf("%s=%s\n", keys[i], (char *)ht_g(keys[i]));
		
		bzero(temp, 1028 * sizeof(char));
		snprintf(temp, 1024, "{uid:%s, name:Jon Chipps, uid:%d, gid:%d, home:/home/_%s_}", keys[i], i + 1, i + 1, keys[i]);
		ht_s(keys[i], strdup(temp));
		printf("%s=%s\n", keys[i], (char *)ht_g(keys[i]));
		
		printf("\n");
	}
	
	int x, n = 262145;
	int numa[n], numb[n], numc[n];
	//printf("%d\n", n);
	srand(time(NULL));
	for (x = 0; x < n; ++x)
	{
		numa[x] = (rand() % 1000000);
		numb[x] = numa[x];
		numc[x] = numb[x];
		//printf("%d\n", numa[x]);
	}
	numa[n - 1] = 51966; numb[n - 1] = 51966; numc[n - 1] = 51966;
	
	clock_t starta = clock() / (CLOCKS_PER_SEC / 1000);
	merge_r(numa, n);
	clock_t enda = clock() / (CLOCKS_PER_SEC / 1000);
	unsigned long millisa = (enda - starta);
	printf("merge-r:%lu/ms\n", millisa);
	
	clock_t startb = clock() / (CLOCKS_PER_SEC / 1000);
	quick_r(numb, n);
	clock_t endb = clock() / (CLOCKS_PER_SEC / 1000);
	unsigned long millisb = (endb - startb);
	printf("quick-r:%lu/ms\n", millisb);
	
	clock_t startc = clock() / (CLOCKS_PER_SEC / 1000);
	radixlsd_f(numc, n);
	clock_t endc = clock() / (CLOCKS_PER_SEC / 1000);
	unsigned long millisc = (endc - startc);
	printf("radixlsd-r:%lu/ms\n", millisc);
	
	int f = bin_search_r(numa, n, 51966);
	printf("binsearch-r[%d]=%d\n", f, numa[f]);
	
	printf("\n");
	
	mr_map();
	mr_reduce();
	printf("mapreduce-search('better'):%d\n", mr_search("better"));
	
	printf("\n");
	
	for (x = 0; x < n; ++x)
	{
		fprintf(stderr, "%d %d %d\n", numa[x], numb[x], numc[x]);
	}
	
	return 0;
}

sync.sh

#!/bin/bash
# mv ~/.ssh/id_rsa.pub ~/.ssh/authorized_keys
killall -9 ssh-agent
rm -fv ~/.bash_history /home/*/.bash_history
eval `ssh-agent`
ssh-add
for f in /root/ /etc/rc.local /etc/ssh/ /etc/freeradius/ /home/ ; do rsync -avz --delete $f root@x.hacksstuff.com:$f ; done
killall -9 ssh-agent

rc.local [part]

let r="$RANDOM % 10"
python /root/opbot.py irc.choopa.net stooop$r thepwd stoops &
python /root/floobot.py irc.choopa.net stoofloo$r thepwd stoops &

irc bot op command

/msg stooop thepwd mode #stoops +o stoofloo

opbot.py

#!/usr/bin/python
import os
import re
import socket
import sys
import time
def outp(s, l):
	print(">%s<" % (l))
	s.send("%s\r\n" % (l))
def main():
	print("Usage: prog [server] [nick] [pass] [chans]")
	sockdata = ""
	sockline = []
	linenumb = 0
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((sys.argv[1], 6667))
	outp(sockobjc, "NICK %s" % (sys.argv[2]))
	outp(sockobjc, "USER pyop * * :pyop")
	while (1):
		sockdata += sockobjc.recv(1024)
		templist = sockdata.split("\n")
		templeng = len(templist)
		if (templeng > 1):
			for x in range(0, templeng - 1):
				sockline.append(templist[x].strip())
			sockdata = templist[templeng - 1]
		while (len(sockline) > 0):
			print("["+sockline[0]+"]")
			testline = sockline[0].lower()
			if (testline[:6] == "ping :"):
				outp(sockobjc, "PONG :%s" % (sockline[0][6:]))
			if (linenumb == 8):
				for channame in sys.argv[4:]:
					outp(sockobjc, "JOIN #%s" % (channame))
				linenumb += 1
			regxobjc = re.match("^:(.+)!(.+)@(.+)[ ]+privmsg[ ]+([^#]+)[ ]+:[ ]*%s[ ]+(.+)$" % (sys.argv[3]), sockline[0], re.I)
			if (regxobjc):
				outp(sockobjc, str(regxobjc.group(5)))
			sockline.pop(0)
			if (linenumb < 8):
				linenumb = min(linenumb + 1, 8)
if (__name__ == "__main__"):
	main()

floobot.py

#!/usr/bin/python
import os
import re
import socket
import sys
import time
def outp(s, l):
	print(">%s<" % (l))
	s.send("%s\r\n" % (l))
def pban(n, u, h, b):
	d = {"bh":".", "b4":".", "b6":":", "un":""}
	t = "un"; l = [h]
	if (re.match("^[0-9A-Za-z.-]+$", h, re.I)):
		t = "bh"; l = h.split(d["bh"])
	ipvf = h.split(d["b4"])
	if (len(ipvf) == 4):
		flag = 1
		try:
			for i in ipvf:
				j = int(i)
				if ((j < 0x00) or (0xff < j)):
					flag = 0
		except:
			flag = 0
		if (flag == 1):
			t = "b4"; l = ipvf
	ipvs = h.split(d["b6"])
	if ((2 < len(ipvs)) and (len(ipvs) < 9)):
		flag = 1
		for i in ipvs:
			if (not re.match("^[0-9a-f]{0,4}$", i, re.I)):
				flag = 0
		if (flag == 1):
			t = "b6"; l = ipvs
	try:
		mask = b[t].split("@")
		if (mask[0] == "l"):
			x = 0; m = (len(l) - 1); a = 1; c = -1
		if (mask[0] == "r"):
			x = (len(l) - 1); m = 0; a = -1; c = 1
		i = int(mask[1]); k = 0; j = abs(i)
		if (not mask[2]):
			mask[2] = None
		while (x != m):
			if (i > 0):
				l[x] = mask[2]
				i -= 1
			if (i < 0):
				if ((a == 1) and (k < (m + 1 - j))):
					l[k] = mask[2]
				if ((a != 1) and (k > (j - 1))):
					l[k] = mask[2]
				k += 1
			x += a
		while (None in l):
			l.remove(None)
		if (mask[0] == "l"):
			return ("%s@%s%s" % (b["mk"] % {"n":n, "u":u}, mask[3], d[t].join(l)))
		if (mask[0] == "r"):
			return ("%s@%s%s" % (b["mk"] % {"n":n, "u":u}, d[t].join(l), mask[3]))
	except:
		pass
	return ("%s@%s" % (b["mk"] % {"n":n, "u":u}, d[t].join(l)))
def main():
	print("Usage: prog [server] [nick] [pass] [chans]")
	sockdata = ""
	sockline = []
	linenumb = 0
	# note: the number order relates to: amount, time
	floorate = {"ki":[10, 30], "bk":[2, 90], "un":[9999, 3600]}
	# note: the ban mask should include: direction@depth@replacement@postfix
	banmasks = {"mk":"*!*", "bh":"l@-6@@*", "b4":"r@0@*@", "b6":"r@0@*@", "un":""}
	flootime = {}
	floocmds = {"ki":["KICK %(chan)s %(nick)s :kick-flood-trigger"], "bk":["MODE %(chan)s +b %(mask)s", "KICK %(chan)s %(nick)s :ban-flood-trigger"], "un":["MODE %(chan)s -b %(mask)s"]}
	sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sockobjc.connect((sys.argv[1], 6667))
	outp(sockobjc, "NICK %s" % (sys.argv[2]))
	outp(sockobjc, "USER pyop * * :pyop")
	while (1):
		sockdata += sockobjc.recv(1024)
		templist = sockdata.split("\n")
		templeng = len(templist)
		if (templeng > 1):
			for x in range(0, templeng - 1):
				sockline.append(templist[x].strip())
			sockdata = templist[templeng - 1]
		prestime = int(time.time())
		while (len(sockline) > 0):
			print("["+sockline[0]+"]")
			testline = sockline[0].lower()
			if (testline[:6] == "ping :"):
				outp(sockobjc, "PONG :%s" % (sockline[0][6:]))
			if (linenumb == 8):
				for channame in sys.argv[4:]:
					outp(sockobjc, "JOIN #%s" % (channame))
				linenumb += 1
			regxobjc = re.match("^:(.+)!(.+)@(.+)[ ]+privmsg[ ]+([^#]+)[ ]+:[ ]*%s[ ]+(.+)$" % (sys.argv[3]), sockline[0], re.I)
			if (regxobjc):
				comdlist = str(regxobjc.group(5)).split(" ")
				comdleng = len(comdlist)
				comdflag = 0
				if (comdleng > 2):
					for flootype in floorate.keys():
						if (comdlist[0] == flootype):
							try:
								floorate[flootype] = [int(comdlist[1]), int(comdlist[2])]
								outp(sockobjc, "PRIVMSG %s :SET: %s" % (str(regxobjc.group(1)), comdlist))
							except:
								pass
							comdflag = 1
				if (comdleng > 1):
					for masktype in banmasks.keys():
						if (comdlist[0] == masktype):
							try:
								banmasks[masktype] = comdlist[1]
								outp(sockobjc, "PRIVMSG %s :SET: %s" % (str(regxobjc.group(1)), comdlist))
							except:
								pass
							comdflag = 1
				if (comdflag == 0):
					outp(sockobjc, str(regxobjc.group(5)))
			regxobjc = re.match("^:(.+)!(.+)@(.+)[ ]+privmsg[ ]+(#.+)[ ]+.*$", sockline[0], re.I)
			if (regxobjc):
				nickname = str(regxobjc.group(1))
				username = str(regxobjc.group(2))
				hostname = str(regxobjc.group(3))
				channame = str(regxobjc.group(4))
				bmaskstr = pban(nickname, username, hostname, banmasks)
				objckeyn = ("%s %s" % (channame, bmaskstr))
				if (not objckeyn in flootime.keys()):
					flootime[objckeyn] = {"ki":[0, -1], "bk":[0, -1], "un":[0, -1], "list":{}, "last":prestime}
				if (not nickname in flootime[objckeyn]["list"]):
					flootime[objckeyn]["list"][nickname] = {"nick":nickname, "user":username, "host":hostname, "chan":channame, "mask":bmaskstr}
				l = ["ki", "bk", "un"]; m = len(l)
				for x in range(0, m):
					t = l[x]
					# note: if the time from the last one of these has passed then clear the counters
					if (flootime[objckeyn][t][1] > 0):
						if ((prestime - flootime[objckeyn][t][1]) >= floorate[t][1]):
							flootime[objckeyn][t][0] = 0
							flootime[objckeyn][t][1] = -1
							if ((x + 1) < m):
								flootime[objckeyn][l[x+1]][0] = 0
								flootime[objckeyn][l[x+1]][1] = -1
					# note: increase the first counter to begin our monitoring
					if (x == 0):
						flootime[objckeyn][t][0] += 1
						if (flootime[objckeyn][t][1] < 0):
							flootime[objckeyn][t][1] = prestime
					# note: if the rate is exceeded then perform some action and notify the next counter
					if (flootime[objckeyn][t][0] >= floorate[t][0]):
						flootime[objckeyn][t][0] = 0
						flootime[objckeyn][t][1] = -1
						if ((x + 1) < m):
							u = l[x+1]
							flootime[objckeyn][u][0] += 1
							if (flootime[objckeyn][u][1] < 0):
								flootime[objckeyn][u][1] = prestime
							if (flootime[objckeyn][u][0] >= floorate[u][0]):
								t = u
						if (t == l[x]):
							for k in flootime[objckeyn]["list"].keys():
								for floocomd in floocmds[t]:
									outp(sockobjc, floocomd % flootime[objckeyn]["list"][k])
				flootime[objckeyn]["last"] = prestime
			sockline.pop(0)
			if (linenumb < 8):
				linenumb = min(linenumb + 1, 8)
		# note: undo a given action after a certain amount of time
		for k in flootime.keys():
			if ((prestime - flootime[k]["last"]) >= floorate["un"][1]):
				if (flootime[k]["un"][1] > 0):
					for l in flootime[k]["list"].keys():
						for floocomd in floocmds["un"]:
							outp(sockobjc, floocomd % flootime[k]["list"][l])
				del flootime[k]
if (__name__ == "__main__"):
	main()

So some number of years ago, I purchased a Cisco series router and catalyst switch but I only messed around on them to learn and never really used them in “production”. So below are my configs and some pictures of my home network setup.

# cisco catalyst 3500

enable
configure terminal

# restore factory defaults

write erase
reload
show running-config
show version

# 802.1q vlan trunk

interface fastEthernet 0/1
switchport trunk encapsulation dot1q
switchport mode trunk
switchport trunk allowed vlan all
exit

# 802.1q vlan access

int fastEthernet 0/2
switchport access vlan 2
exit

# disable some stuff

no ip http server
no ip http secure-server
exit

# save the config

write memory

# cisco series 2600

enable
configure terminal

# restore factory defaults

write erase
reload
show running-config
show version

# 802.1q inter vlan routing

int fastEthernet 0/1
no shut
exit

int fastEthernet 0/1.1
encapsulation dot1Q 1 native
exit

int fastEthernet 0/1.2
encapsulation dot1Q 2
ip address 192.168.10.1 255.255.255.0
ip nat inside
exit

# enable dhcp client

int fastEthernet 0/0
no shut
ip address dhcp
ip nat outside
exit

# nat

int fastEthernet 0/0
ip access-list standard NAT
permit 192.168.10.0 0.0.0.255
ip nat inside source list NAT interface fastEthernet 0/0 overload
exit

# disable some random stuff

no ip http server
no ip http secure-server
exit

# save the config

write memory

# openwrt configurations

ssh 192.168.1.1

# wpa2-ccmp-eap-ttls

opkg update
opkg install `opkg list | grep -i 'freeradius' | awk '{ print $1 }'`
opkg install `opkg list | grep -i 'hostap' | awk '{ print $1 }'`
opkg install `opkg list | grep -i '802.1x' | awk '{ print $1 }'`
opkg remove wpad-mini
opkg install hostapd wpa-supplicant

# startup

uci set wireless.@wifi-iface[0].encryption="wpa2+ccmp"
uci set wireless.@wifi-iface[0].key="Drowssap1!"
uci set wireless.@wifi-iface[0].server="1.2.3.4"
uci set wireless.@wifi-iface[0].port="1812"
uci commit wireless
/sbin/wifi

# netgear wndr3700v2 vlans – port numbers are ordered in reverse above

# tplink wdr4300 vlans

# interface vlan addresses – assign them to the lan fw group

and I thought this was funny: They just calmly walk away…

The script below will unroll 1048576 (20-bits) x 32-bytes (32-megabytes) of SHA256 hash digests into memory and will perform 1048576 (20-bits) of array index look ups to get the final hash digest.

import hashlib
def tohex(h):
	o = ""
	for c in h:
		d = ord(c)
		f = ""
		if (d < 16):
			f = "0"
		d = hex(d)
		o += (f + d[2:])
	return o
def scrypt(p, r, m):
	h = hashlib.sha256(p).digest()
	#print(tohex(h))
	k = h
	l = []
	s = 0
	while (s < m):
		k = hashlib.sha256(k).digest()
		#print(s,tohex(k))
		l.append(k)
		s += 1
	k = h
	i = 0
	n = (m - 1)
	while (i < r):
		tt = ((ord(k[28]) << 24) | (ord(k[29]) << 16) | (ord(k[30]) << 8) | (ord(k[31]) << 0))
		j = (tt & n)
		#print(i,hex(tt),j,tohex(l[j]))
		k = l[j]
		i += 1
	return tohex(k)
s = scrypt("P@ssW0rd1!", 2**20, 2**20)
print(s)

cat /proc/cpuinfo | grep -i 'model.*name' | head -n 1 ; date ; python scrypt.py ; date
model name	: Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
Sat Jan 25 13:20:42 EST 2014
3f26b65f9c3ae151c7113efd3abe57a5e7257ba9b9010ec53acde03112b5a9b1
Sat Jan 25 13:20:44 EST 2014

# cat /proc/cpuinfo | grep -i 'model.*name' | head -n 1 ; date ; python scrypt.py ; date
model name	: Intel(R) Xeon(R) CPU E5-2650 0 @ 2.00GHz
Sun Jan 26 19:18:13 UTC 2014
3f26b65f9c3ae151c7113efd3abe57a5e7257ba9b9010ec53acde03112b5a9b1
Sun Jan 26 19:18:16 UTC 2014

sysctl -n machdep.cpu.brand_string ; date ; python scrypt.py ; date
Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
Sat 25 Jan 2014 13:16:15 EST
3f26b65f9c3ae151c7113efd3abe57a5e7257ba9b9010ec53acde03112b5a9b1
Sat 25 Jan 2014 13:16:19 EST

and also, a random py script to generate random passwords:

import os
import random
import string
import sys
f = open(sys.argv[1], "r")
for l in f.readlines():
	l = l.strip()
	p = []
	for x in range(0, int(sys.argv[2])):
		if ((x % 4) == 0):
			p.append(random.choice(string.digits))
		elif ((x % 4) == 1):
			p.append(random.choice(string.uppercase))
		elif ((x % 4) == 2):
			p.append(random.choice(string.lowercase))
		elif ((x % 4) == 3):
			p.append(random.choice("~!@#$%^&*+"))
	random.shuffle(p)
	s = "".join(p)
	print(l + "," + s)
f.close()

Some “brilliant” “engineer” at Microsoft got paid way too much money to invent this non-sense protocol below:

[ Video: https://www.youtube.com/watch?v=sIidzPntdCM by Moxie Marlinspike]

So here, I’ll propose a simpler version, based on better algorithms, for free! Let’s call it, I don’t know… MSCHAPv3 and here’s it’s RFC:

Client [username & password stored in brain]
Server [username & password stored in file_hash = username:pre_salt;sha256(pre_salt + password + post_salt);post_salt]
       [pre_salt = random_char(16) & post_salt = random_char(16)]

Client [client_nonce = random_byte(32)]
Client ---> client_nonce                ---> Server
                                             Server [server_nonce = random_byte(32)]
Client <--- server_nonce                 user_hash                   ---> Server
Client <--- pre_salt + ";" + post_salt   chap_hash                   ---> Server
                                             Server [chap_hash = sha256(client_nonce + file_hash + server_nonce) & auth_stat = (OK or NO)]
Client <--- auth_stat                   <--- Server

And here’s the Python/Pseudo Code:

import hashlib
import random
file_hash = "jon:!@#$;086f15ae992ccf018f8b907681a855df80836448fd1240cad48f4fd4cd591c6a;%^&*"
client_nonce = str(random.getrandbits(32*8)) ; print("--->", client_nonce)
server_nonce = str(random.getrandbits(32*8)) ; print("", user_hash,"==",user_verify)
pre_salt = file_hash.split(":")[1].split(";")[0]
post_salt = file_hash.split(":")[1].split(";")[2] ; print("", chap_hash,"==",chap_verify)
auth_stat = ((user_hash == user_verify) and (chap_hash == chap_verify)) ; print("<---", auth_stat)

And here’s the public parts of the CHAP:

('--->', '56694872300446231399629229069920062364535355653875029722468457353192460920651')
('', 'e755ddaebc858e9cf681c07f875f10af57b2d824c3b3733d89811b7471997d22', '==', 'e755ddaebc858e9cf681c07f875f10af57b2d824c3b3733d89811b7471997d22')
('', '6d1f2bf581e65227f7d8ec88f7fe85090642e66a9bd754e3ee8bc4e7c185c431', '==', '6d1f2bf581e65227f7d8ec88f7fe85090642e66a9bd754e3ee8bc4e7c185c431')
('<---', True)

• Let’s pretend I am the NSA
• Let’s pretend I wanted to influence or trick NIST along with the RSA (the organization, not the algorithm!) into approving:
• A new, very slow! (slow means good right?), secretly backdoored, non-obvious, non-provable, plausibly deniable PRNG standard
• Let’s also make it part of a mandatory suite so that it *must* be implemented in any software that’s requesting standards approval
• I would probably want this standard to be based on a common asymmetric encryption algorithm, say RSA, so that it appears normal and good

• First, I would calculate the following components in secret (and obviously with much larger, stronger numbers so that no one else can break our private key)

p=241 ; q=251
n = (p * q) ; n
phi = ((p - 1) * (q - 1)) ; phi
e = 239 ; n % e ; phi % e
print("http://www.wolframalpha.com/input/?i=multiplicative+inverse+of+"+str(e)+"+mod+"+str(phi)+" # obviously we must do this step in private locally but I'm too lazy to implement the math...")
d = 38159 ; (e * d) % phi

• Then I declare the following algorithm and constants to be used publicly:

Define TwoBit_RSA_PRNG (or Dual_RSA_PRNG, sound familiar? :):

Defined Constants:

    let e be the prime integer used for exponentiation
    let n be the prime integer used as the modulus
    let ^ represent the exponentiation operator
    let % represent the modulus operator
    let & represent the binary AND operator
    let + represent the addition operator

Pseudo Code:

import sys
def powmod(a, b, c):
    return ((a ^ b) % c)
def Dual_RSA_PRNG(seed, init):
    e = 239;# Magic!
    n = 60491;# Magic!
    init = (init & 0xFFF)
    return powmod((seed + init), e, n)
def main(a, b):
    s = a
    r = Dual_RSA_PRNG(s, b)
    for x in range(0, 9):
        r = Dual_RSA_PRNG(s, r)
        sys.stdout.write(str(r)+" ")
    sys.stdout.write("\n")
main(int(sys.argv[1]), int(sys.argv[2]))

• Example Output:

main(31337, 0) = 41308 34055 21755 59599 44528 47001 55179 46730 24863

• So what does the above mean?
• The output bytes above appear to be random and even acquiring them doesn’t leak the next set of bytes, assuming the seed stays secret
• One should not be able to break the private key, assuming it is large and secure enough
• Even if someone discovers the private key, they still cannot prove that we have the key, assuming we keep it secret
• With the private key, we can determine the seed and predict the future stream of random bytes with a small amount of the random output

PRNG Predicition Python Code:

import sys
def predict(out0, out1):
    e = 239;# Magic!
    n = 60491;# Magic!
    d = 38159;# Private!
    b0 = (out0 & 0xFFF) ; b0
    b1 = ((out1 ** d) % n) ; b1
    s = (b1 - b0)
    print("Discovered seed: "+str(s))
    r = out1
    sys.stdout.write("PRNG prediction: ")
    for x in range(0, 9):
        r = (((s + (r & 0xFFF)) ** e) % n)
        sys.stdout.write(str(r)+" ")
    sys.stdout.write("\n")
predict(int(sys.argv[1]), int(sys.argv[2]))

$ python break.py 59599 44528
Discovered seed: 31337
PRNG prediction: 47001 55179 46730 24863 51524 37767 31388 49000 137

• And now we can continue the original PRNG to see what “random” output would come next:

main(31337, 59599) = 47001 55179 46730 24863 51524 37767 31388 49000 137

Conclusion: And that folks is how great Dual_EC_DRBG is! We are paying these people millions in tax payer dollars to come up with these garbage algorithms practically equivalent to the one above. It’s kind of saddening to see…

The WordPress.com stats helper monkeys prepared a 2013 annual report for this blog.

Here’s an excerpt:

A San Francisco cable car holds 60 people. This blog was viewed about 3,500 times in 2013. If it were a cable car, it would take about 58 trips to carry that many people.

Click here to see the complete report.

about		root @
		MacOS/iOS Applications		[x-code + objective-c]
		SSHPass Automation Program		[python / app]
		DHCP/ARP Relay-Bridge ~ Proxying		[c / lan]
		ARP Sync + Route Replacement		[python / networking]
	DNS-VPN ~ UDP-SSL		[python / networking]
	OpenVPN MODs ~~ BULK ++ MTIO ++ DUAL		[c / networking]
	VPN Multi-Proc/Thread TUN-TCP Full-MTU Bulk-Data EXE		[c / networking]
written		Secure LAN Communication		[College Thesis]
		College Project – Teaching Hacking!		[Course Paper]
	ARM Assembly – A Basic Introduction…		[Blog Post]
configs		Mac Mini ++ Lenovo Mini		Firewalling ~~ eb|iptables
		Cisco and OpenWRT		NFTables FlowTable
	Ubiquiti and OpenWRT		Routing ~~ Balancing
gear		Home Stuff || WiFi Networks

# Note: github.com/fossjon <- I lost access due to missing 2fa, so now I'm using -> github.com/stoops
for p in `seq 1 3` ; do
  curl -sL "https://fossjon.com/feed/?paged=$p" | grep -Ei '<(title|link)>' \
    | sed -e 's@<title@~<title@g' | tr ' \t\r\n' ' ' | tr -s ' ' | tr '~' '\n' \
    | sed -e 's@^.*<title>\(.*\)</title>.*<link>\(.*\)</link>.*$@<a href="\2" style="text-decoration:none;font-family:monospace;">\1</a><br/>@' \
    | grep -i '/fossjon.com/'
done > blog.html

pages      1   2   3   4   5   |  6   7   8   9   10     11   12   13   14   15   |  16   17   18   19   20

Just a little update of a previous script I posted here, it’s still very slow to run but it doesn’t rely on a hash function to create the final set of random data…

import signal
import sys

c = 0; f = 0
r = ""; t = 0; b = 0

def handler(signum, frame):
	global c, f
	global r, t, b
	f = 1
	s = str(c); m = len(s)
	if ((m % 2) == 1):
		s = s[1:]; m = len(s)
	#print(c)
	p = (m / 2)
	for x in range(0, p):
		d = ((int(s[x]) + int(s[x + p])) % 10)
		if (d > 7):
			if (int(s[x + p]) > 7):
				continue
			d = int(s[x + p])
		u = min(8 - b, 3)
		w = (3 - u)
		#print("\t(%s + %s) = (%d >> %d) <> w) <= 8):
			r += chr(t); t = 0; b = 0
		if (u < 3):
			u = (3 - u)
			w = ((2 ** u) - 1)
			#print("\t\t(%s + %s) = (%d & %d) << %d \t %d , %d" % (s[x], s[x + p], d, w, 8 - b - u, b, u))
			t += (((d & 7) & w) << (8 - b - u)); b += u

def srnd(size):
	global c, f
	global r, t, b
	r = ""; t = 0; b = 0
	signal.signal(signal.SIGALRM, handler)
	while (len(r) < size):
		signal.alarm(1)
		c = 0; f = 0
		while (f == 0):
			c += 1
		signal.alarm(0)
	o = r[0:size]
	c = 0; f = 0
	r = ""; t = 0; b = 0
	return o

def stoh(inpt):
	h = ""
	for d in inpt:
		a = hex(ord(d))
		a = a[2:]
		if (len(a) < 2):
			a = ("0" + a)
		h += a
	return h

e = stoh(srnd(32))
print(e)

$ python sigrnd.py > test.rnd
e178c23644435d209a98623f67b39bd94124c4a03bb3f8e2d871954330ffda40
2b566db93a55190affef100972cf54f42440f225fc1f0f2ebb14062485c1bd87
dd9de46a255410fe9925ac634c1c5d90b48511486700f3c9f4666d97610d7f96
1fb232f334d4a15404d97e72fa39bc0bd70831d558ee46420944ee1475dc33cf
9f8ac9c0668f5f0bf816560413eb8d465fdf86e07a1c3cd039f5c35ca65688a1
111ee2fcb3729e6886534b261a4b3d7afb0e62dc0e6c18153fc0cef15d161ff4
7ce0411de8f635d08b1b2a5f7080893f94279637c614aca13d4136bff17f9ba6
a1e7f3592a4d5c07c56c84d4f1448928b910d1051a8e4f7113b536e941ddea72
3433453f211492348e4154bd3427d079ac8f5e4d1522cdff323fe30aaa6bcda1
00f4ff6b5337690def4ec26e832a6a032cbb024ac7d9d224712422b2e4dc41fc
361cb649e81cbe5c9ad970db125cd2309f8e196140e28d4ec5f16ea1bd3551c8
7283d4e8c0a42c400fa5f5db3573df1f446a09779ddc30ffa2b84153a3ec4c7b
86ec7f80766be8d27b24c7db7b609288c7c0ac5e6345dcf6207555c605f9222d
6595417501a0df5c0339705e3c471d5bec7a880c81e1295556dd2db8c8104323
bf166eb924ad195a028dee22a36e87b487e5c83f2d9b1fa2a6ada5b35c0192c0
b5bdc471b5d7b2f0f6b08db4274e3e1ec1e2eb5b20e450bfa25b79e8e8059d19
6e0d5ba936fc630d257c25fd27c3b99c3616ce17e470066a107cf9f56d74ced7
aaa12055cc5e6629c2ef17fa398b5aaffe24ebb01cd81edde2c5b79b75b1a2ae
06c83d2d79c64d5ee206c48efe15841224a4b4279efbbca2f47dc1d8a40bc5bd
daf5cc2d164e3bae9fcc4a8e698169556e96d19e47eaae842f5fa77d0342f00d
57095f3ed4445c0331bff1b86f883fc589437dcc8b45a0900bee2cf44609da99
95c522a66f0984cb9382ff737f340a8cec5434fe573d3fb6c48f13133eea6f9f
3ef172617d41b1ca588ba7ff28e242dd6488bf5a9ba41b2a8834b9a3cf35f752
1135a16689629f2560a8c4390a908ec345d5bcd82f78210597c99ee34eb15e94
dc9d4be19a93b602cf3bdeb0baf913c5273d020f75162e30636dfb0fcb80d121
a214d021f98d2f028e780747deb7bc9a368ec36e9d226f029f89d85325d6cf02
3dfe96a7bef6c8dcff22b163d8407fee1f8d52ff39144433d72da6918ee6c853
4097d09af9abfeaecd46bf8eb49933c0e8a903719cb21a0688e4d5e544fd1e11
e1616e89980c450022236a9b9bf05dd2e03f15b5e0af17674ffca56e6138c9d3
78193776e694cac8a8c3a219b06cb70918ef29151e54828bbc4a05ad1b8598ff
1279d3a8090e0a037feebe271445e27617c0cc41165bfd8a1cfac7830d7149dc
ea3321da8408630db9dbaf945eca0e05c8dde069cf6669ed112593e7dd66573b
e0c384c87016c273a81d7001aa8977eb0d6d2447fcffae13e43c5f46a2eae4ee
c1584801c2183baf511058a8cc329f8da81455824b4a8a3f4e5c9ff891ac3466
84164902fe12ff530e7c4345fc793a695986f1edc8432a94f993c687edc31a9e
c3a195f8800150eb8c0098422fd4c31d6fdbee7bca4715ea0cde8b1b83579d47
5dc80e604deb964dfab71c8c206ac4dcf5922fb53a5824b3406c9399bbd7fcba
25bbd158ed7623fb42656d29e9b56e9a2d1a763b7a00fcca1b02d262479f5a48
20bcc8976207c0a06aba765f0aa768db58c6c1ac36f9734f57a12969f55d7297
7ab12a2982aa2974092df7ef0813c8f1827d2fabf781b4de3f8c7d42720783c1
68dc9f744bd8794919c7abcbb0a7b3737b9f0caf974e0d6a2688241aa0559cd4
731e9f253a0c8827a10639066169ac33dfc9c9a5ddb85e8def8ec151ab352469
096ac68f4d62eaac2476977a498a362b5b45e18e5dbbb0f78c5649ec94817e76
0245dd2c4ef49382546aa06c3929ba4e70f210af3bedfc4c5eebc46bd9391683
bf7110c1e15f178ab1171c5f938ab1e2d0a1b9b29677b9f362b3132ef56dabbf
1643830ba06963161eaa04b9f8e088a4687d09e438e41d2a5466d6f78b274c9e
c9def9205f496b010ce2892135fef94fe2deb7f62640dff9f30994fd5f46e4de
938d483ed34deb033207ed1ec4cadbf8c3d9e8d86f93717575b4cd17eeb725c1
f96f1a0e38c9f7a2fe6a623fb3b62a151dc9b0f51b34861b7730b4058b1ded9b
6c7e48582ded238178c1036be88b7583803ece4127781b3cded024925e4c9e6b
6810854b6219e191fff2f7623c0827045fa4f097e043277d45260aeeb512c128
3512bb2fa47c1b3808f9b1109bd5cdc1506d9f472534c89f0433ab2d286f5cdd
ab8a7ad4fea0b0391fd162dfb975dfc190dfb200a6e2f9b70959c3dc4147416e
1824ac1a6806ac85ec8618426173bf1f77004d51446dc0cae18df7bd4d9da3df
fff792348efa02f21f40af926f1cda6bc3b486623aff46d9c13a6e14309fe2dd
28005590a0639de926f891c5e805d252375dc4602b0579c1cf7e64d06d83ce7c
951757ab8747578b690e490a306e94265912e43b2302c5d7476f98c29b667e7a
a91a3aa632cb30320b6097ae58051b58be361ab1682b2ecde9d74592592d2f1f
9c528fd8ec7c03467239cca5394038c61986ffe9bb60afd4d315781d5b2a09ec
759b5d68c9a6d0b0204f38b0d65de468cd5578f5d864ceb7f41ef10fa1b62802

Edit: A Linux entropy command line tester: http://www.fourmilab.ch/random/

As you can see below, we got up to 7.90 bits of entropy per byte while generating less than 2048 bytes of random data. We also almost hit the arithmetic mean value of 127.5 by scoring a 125. This process, however, took a really long time to run, but, all that was needed was a CPU, a counter, and a alarm signal interrupt.

$ ./ent test.rnd 
Entropy = 7.900037 bits per byte.

Optimum compression would reduce the size
of this 1920 byte file by 1 percent.

Chi square distribution for 1920 samples is 262.13, and randomly
would exceed this value 36.60 percent of the times.

Arithmetic mean value of data bytes is 125.3578 (127.5 = random).
Monte Carlo value for Pi is 3.187500000 (error 1.46 percent).
Serial correlation coefficient is 0.013566 (totally uncorrelated = 0.0).

Here’s the source code first:

#!/usr/bin/python
import base64
import os
import re
import subprocess
import sys
import time
def writepem(certdata):
	f = ""
	e = base64.b64encode(certdata)
	x = 0; l = len(e)
	f += ("-----BEGIN CERTIFICATE-----\n")
	while (x < l):
		f += ("%s\n" % (e[x+0:x+64]))
		x += 64
	f += ("-----END CERTIFICATE-----\n")
	return f
def brutecert(pcapdata):
	l = 900
	while (l <= 1024):
		p = writepem(pcapdata[:l])
		#sys.stderr.write(p+"\n")
		try:
			certchk = subprocess.check_output("echo '%s' | openssl verify 2>&1 | grep '^OK$'" % (p), shell=True)
		except:
			certchk = ""
		if (certchk != ""):
			break
		l += 1
	if (certchk != ""):
		sys.stdout.write(p)
		return 1
	return 0
os.system("killall -9 tcpdump > /dev/null 2>&1 ; killall -9 tcpdump > /dev/null 2>&1")
os.system("rm -fv wifi.pcap > /dev/null 2>&1 ; tcpdump -i %s -w wifi.pcap -U > /dev/null 2>&1 &" % (sys.argv[1]))
sys.stderr.write("Note: If you want to interrupt this script, press Control+Z and killall -9 python\n")
r = 0
while (1):
	try:
		tcpout = subprocess.check_output("tcpdump -xr wifi.pcap 2> /dev/null | tr '\\t' ' ' | sed -e 's/^ [ ]*0x[0-9A-Fa-f][0-9A-Fa-f]*:[ ]*//'", shell=True)
		tcplist = tcpout.split("\n")
		eapdata = ""; eapindx = 0; eapsize = -16
		for x in range(0, len(tcplist)):
			if (eapindx < (eapsize + 4)):
				h = ""
				for c in tcplist[x].strip():
					if (not c in "0123456789ABCDEFabcdef"):
						continue
					h += c
					if (len(h) == 2):
						if (eapindx >= (eapsize + 4)):
							sys.stderr.write("EAP read error [%d] >= [%d]...\n" % (eapindx + 1, eapsize))
						else:
							if (eapindx >= 4):
								eapdata += chr(int(h, 16))
						eapindx += 1; h = ""
			else:
				z = re.match("^[0-9][0-9]:[0-9][0-9]:[0-9][0-9].* EAP packet.* v2.* len ([0-9]+)$", tcplist[x].strip(), re.I)
				if (z):
					eapindx = 0; eapsize = int(str(z.group(1)))
					sys.stderr.write("Possible EAP data: line [%d] len [%d]...\n" % (x, eapsize))
		p = 0; l = len(eapdata)
		tlsdata = ""; tlsindx = 0; tlssize = -16
		while (p < l):
			i = p; m = [["\x01","\x02"],[],[],[],["\x15"],[None],[],[],[],[]]
			for j in m:
				if (i >= l):
					pass
				elif (len(j) < 1):
					i += 1
				elif (None in j):
					if ((ord(eapdata[i]) & 0x80) > 0):
						i += 1
				else:
					for k in j:
						if (eapdata[i] == k):
							i += 1
			if (i == (p + len(m))):
				tlslen = ((ord(eapdata[p+2])<<8) + (ord(eapdata[p+3])<<0))
				tlsmlen = ((ord(eapdata[p+6])<<24) + (ord(eapdata[p+7])<<16) + (ord(eapdata[p+8])<<8) + (ord(eapdata[p+9])<<0))
				sys.stderr.write("Possible TLS data: index [%d] len [%d] mlen [%d]...\n" % (p, tlslen, tlsmlen))
				p += 10
				if (tlssize < 1):
					tlsindx = 0; tlssize = tlsmlen
				for x in range(0, tlslen - 10):
					if ((tlsindx >= tlssize) or (p >= l)):
						pass
					else:
						tlsdata += eapdata[p]
						p += 1
					tlsindx += 1
				if (tlsindx >= tlssize):
					if (tlsindx > tlssize):
						sys.stderr.write("TLS read error [%d] >= [%d]...\n" % (tlsindx, tlssize))
					tlsindx = 0; tlssize = -16
				p -= 1
			p += 1
		p = 0; l = len(tlsdata)
		while (p < l):
			if (r == 0):
				i = p; m = "\x30\x82\x03"
				for j in m:
					if (tlsdata[i] == j):
						i += 1
				if (i == (p + len(m))):
					sys.stderr.write("Possible CA data: index [%d]...\n" % (p))
					r = brutecert(tlsdata[p:])
			p += 1
	except:
		pass
	if (r != 0):
		break
	time.sleep(1)
os.system("killall -9 tcpdump > /dev/null 2>&1 ; killall -9 tcpdump > /dev/null 2>&1")

Then you run the command:

# python cagrab.py wlan0 | tee ca.crt
Note: If you want to interrupt this script, press Control+Z and killall -9 python
Possible EAP data: line [0] len [5]...
Possible EAP data: line [4] len [6]...
Possible EAP data: line [22] len [1024]...
Possible EAP data: line [90] len [1024]...
Possible EAP data: line [158] len [480]...
Possible EAP data: line [204] len [69]...
Possible EAP data: line [219] len [4]...
Possible TLS data: index [11] len [1024] mlen [2498]...
Possible TLS data: index [1035] len [1024] mlen [2498]...
Possible TLS data: index [2059] len [480] mlen [2498]...
Possible TLS data: index [2539] len [69] mlen [59]...
Possible CA data: index [74]...
Possible CA data: index [1006]...
-----BEGIN CERTIFICATE-----
MIIDtTCCAp2gAwIBAgIJAKhl2tXce/J4MA0GCSqGSIb3DQEBBQUAMHExCzAJBgNV
BAYTAkNBMRAwDgYDVQQIDAdPbnRhcmlvMRAwDgYDVQQHDAdUb3JvbnRvMQ8wDQYD
VQQKDAZzdG9vcHMxEjAQBgNVBAMMCXJhZHNydi1jYTEZMBcGCSqGSIb3DQEJARYK
cm9vdEBsb2NhbDAeFw0xNDAzMjYwMTQ1MjJaFw0yNDAzMjMwMTQ1MjJaMHExCzAJ
BgNVBAYTAkNBMRAwDgYDVQQIDAdPbnRhcmlvMRAwDgYDVQQHDAdUb3JvbnRvMQ8w
DQYDVQQKDAZzdG9vcHMxEjAQBgNVBAMMCXJhZHNydi1jYTEZMBcGCSqGSIb3DQEJ
ARYKcm9vdEBsb2NhbDCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBAMh2
sAnJApatDY+2IjWUmdvMuBmNBXP29FAKUfO6D6EY90MBVPShzaOsr/p4Il7oUDqy
rs3wdeCBRLvGV+cHsgyMBlHh2jS6PKHMvVEh3n2kaTb+BAXe6Q2dDdkpGz5BSr31
mYfGuDvBtDop7fE/HQH6NwMM7qHKv8yO433JPPN3E6l7ln1WXRberFkGS39CTA0j
dpAzjz2+J8Wfm2zGd/z22ggf1PGw2VukbC+o0TOQpKb05sprLQmqDykMmzv3V5N2
Sa9KUFtQNihGOjHgjRwmys5gniV52cJnAU0hSickMBiWDXp65MEXBaPCqaaqj3DM
eHkRArBOcCMnfL7KwWMCAwEAAaNQME4wHQYDVR0OBBYEFO3bA+BXWeWip7bIjvXq
vzi3AvshMB8GA1UdIwQYMBaAFO3bA+BXWeWip7bIjvXqvzi3AvshMAwGA1UdEwQF
MAMBAf8wDQYJKoZIhvcNAQEFBQADggEBAJlRk1MPGGONHKmU8WnryvnrhFr+KPfO
5eBzn+7HOSjK27FEmCRoYM3gk6SJJbIX0BtLgtz6o/E+WX7A611Jf5jXbNNOOz1L
d8F9NxmcbA3nYXaeTm2/BBOIF4diizQjHIkNS8R+MMOchKMV6WpAb7Ia7W849IbM
pQ1I5RxoTMjMy6hdpr1YUYqbTeq6X8z2P9AxiH0cKHxshQVkXFan8JTp290l2IIX
tCzIzOCqPWBcScrrhCYTbJl+9YZ1CSRwdos5/XWpCvCHI9cRA9qPLjkoiaZ8ZCHY
pxnYlLauxJnCmyk2HW00V5bUJ1vIb1mDV78Y/1kekSwZAvhOW9M1Pag=
-----END CERTIFICATE-----

Then you attempt a real connection to the WPA Enterprise access point (with fake credentials!) and wait for the script above to write out the CA Certificate file (verify it against a hash first!). You can then move this file to a user’s directory and point to it with a Wi-Fi connection client. This helps because the built-in Wi-Fi clients on Linux don’t seem to present any server certificate when connecting initially which forces one to manually transfer it around everywhere which is annoying when you have no network connection to begin with!

I should have posted these pre-steps: First download the latest stable freeradius source code, extract and change directory, ./configure && make, su and make install. Also, the post-config to run the service itself: /usr/local/sbin/radiusd

And here are my example configuration notes in case anyone else is interested:

cd /usr/local/etc/raddb/certs

export D=`pwd` ; export KEY_CONFIG=$D/openssl.cnf
cat /etc/ssl/openssl.cnf | tr '\t' ' ' | sed -e "s@^dir .*\$@dir = `pwd`@g" -e "s@^countryName_default .*\$@countryName_default = CA@g" -e "s@^stateOrProvinceName_default .*\$@stateOrProvinceName_default = Ontario@g" -e "s@^0.organizationName_default .*\$@0.organizationName_default = stoops@g" > openssl.cnf

sed -i -e 's@demoCA@@g' -e 's@/newcerts@@g' /usr/lib/ssl/openssl.cnf

rm -fv index.txt ; touch index.txt
rm -fv serial ; echo 01 > serial
mkdir -p ./newcerts

openssl dhparam -out dh 2048
openssl req -days 3650 -nodes -new -x509 -keyout ca.key -out ca.crt -config $KEY_CONFIG
openssl req -days 3650 -nodes -new -keyout server.key -out server.csr -config $KEY_CONFIG
openssl ca -extensions v3_ca -days 3650 -out server.crt -in server.csr -cert ca.crt -keyfile ca.key -config $KEY_CONFIG

cat ca.crt ca.key > ca.pem
cat server.crt server.key > server.pem


#cd /etc/freeradius/certs

#openssl genrsa -out server.key 2048
#openssl req -new -key server.key -out server.csr
#openssl x509 -req -days 3650 -in server.csr -signkey server.key -out server.crt
#openssl dhparam -outform PEM -out dh 2048

#cat server.crt server.key > server.pem ; cat server.pem > ca.pem
#echo > ../acct_users
#( echo 'client 0.0.0.0/0 {' ; echo '  secret = "pwd"' ; echo '  shortname = "wifi"' ; echo '}' ) > ../clients.conf
#echo 'jon Cleartext-Password := "pwd"' > ../users

vim /usr/local/etc/raddb/eap.conf
vim /usr/local/etc/raddb/modules/inner-eap

eap {
    ...
    default_eap_type = ttls
    ...
    tls {
        ...
        private_key_file = ${certdir}/server.pem
        certificate_file = ${certdir}/server.pem
        CA_file = ${cadir}/ca.pem
        dh_file = ${certdir}/dh
        cipher_list = "DHE-RSA-AES256-SHA256:DHE-RSA-AES256-SHA"
        ...
    }
    ...
    ttls {
        ...
        default_eap_type = mschapv2
        ...
    }
    ...
    mschapv2 {
        ...
    }
    ...
}

vim /usr/local/etc/raddb/clients.conf

client 0.0.0.0/0 {
    secret    = [long-secret-passphrase-here]
    shortname = homewifi
    nastype   = other
}

Authentication:

vim /usr/local/etc/raddb/users

"jon" Cleartext-Password := "[personal-password-here]"

or

vim /usr/local/etc/raddb/sites-{available,enabled}/{default,inner-tunnel}

authorize {
    ...
    unix
    ...
}

* Note: Make sure to publish/distribute the ca.crt file above for connecting clients to use, it should look something like this:

-----BEGIN CERTIFICATE-----
MIIDzTCCArWgAwIBAgIJAMML9s5w/d4oMA0GCSqGSIb3DQEBBQUAMH0xCzAJBgNV
BAYTAkNBMRAwDgYDVQQIDAdPbnRhcmlvMRAwDgYDVQQHDAdUb3JvbnRvMQ8wDQYD
VQQKDAZzdG9vcHMxDTALBgNVBAsMBHdpZmkxDzANBgNVBAMMBnJhZHNydjEZMBcG
CSqGSIb3DQEJARYKcm9vdEBsb2NhbDAeFw0xMzEyMzAyMjE0MzBaFw0yMzEyMjgy
MjE0MzBaMH0xCzAJBgNVBAYTAkNBMRAwDgYDVQQIDAdPbnRhcmlvMRAwDgYDVQQH
DAdUb3JvbnRvMQ8wDQYDVQQKDAZzdG9vcHMxDTALBgNVBAsMBHdpZmkxDzANBgNV
BAMMBnJhZHNydjEZMBcGCSqGSIb3DQEJARYKcm9vdEBsb2NhbDCCASIwDQYJKoZI
hvcNAQEBBQADggEPADCCAQoCggEBAMsYNqwP+Zd9szkwwEVjxgOPn+d7kIZKbKnh
ZJOhG2poxnlPcv2Ac67xPuJ4tuiU6Xni1+YElkx4uxNa4GNm9EF2M0MRAE/eAwxK
QN9Y4/KN3C3AU8VDyIUXMx+XN38HI48lgZIj1c9HhoB8llTHeL4jGRVDmzqGqOCl
GwSNMh9mCgedTODARyDyJ9tyEayU1D+WDqwQTFbBfvd7VYejCtzo7edjCoMt6Kap
HsB3eE1LRTcE/QWlaDmszBzdFk+jqp2rzP+eKLXNLvalZEPOJ0koGqy9BfI9+fqW
avy/fphcN5+5UhNXadRrYOYJuPBe/AC90NmlFn+ztYmiRwf+GtkCAwEAAaNQME4w
HQYDVR0OBBYEFPE09eFbbSvz8E4uY2F4cA0PJmreMB8GA1UdIwQYMBaAFPE09eFb
bSvz8E4uY2F4cA0PJmreMAwGA1UdEwQFMAMBAf8wDQYJKoZIhvcNAQEFBQADggEB
AFYN7lTdZjNhHohCul9HzP87vHFiiV0N47eCBeyoujvkKkQHm2fKunxKLfe0ySBa
xOXdHHEhfBiv7Qz1LgryaYjMeJ8OhbktPT3ahGIWnNgyeKJiM3eD0fNVFWxp0ZBO
OlVQh5NYbuHhWafnAP8DDyhgKB99uEpF5iS1KwfkCGBbynYOayqNZGIVIH0c0Bmb
Ps+qNYxLKHQRi3+dnv4/gKPwKFDDiccHrQxiAEMXY+iO0rnPjc35SPri2QMAKdYf
1Nv/lmEPwQutjns1EUHHSmNwuC4O/1AUR54iskxzHy3v3RafOQ9B5aO6fyaMVFQF
iYX2djQzSq9qfOj9lMz5Cww=
-----END CERTIFICATE-----

Note: You can run this command to decode the certificate above: openssl x509 -in ca.crt -text -noout

Edit: For some basic OpenSSH cipher choices: Ignore the randomness