arp.c

/*

arm-linux-gnueabi-gcc -static -march=armv7 -o arp.arm arp.c ; chmod 700 arp.arm

./arp.arm "s" "br0" "/jffs/etc/freeradius/users" "10.0.0.20" "10.0.0.200"


gcc -Wall -o arp.xes arp.c ; chmod 700 arp.xes

read -p "pwd: " -s p ; echo ; echo "$p" | ./arp.xes "c" "en0"

*/

#include <arpa/inet.h>
#include <netinet/in.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <sys/socket.h>
#include <time.h>
#include <unistd.h>

#include "sha256.c"

typedef struct userinfo {
	char *i;
	unsigned long t, l, a;
} infodata;

void strp(char *cstr, int clen)
{
	cstr[clen] = '\0';
	while ((clen > 0) && ((cstr[clen-1] == '\r') || (cstr[clen-1] == '\n')))
	{
		--clen;
	}
	cstr[clen] = '\0';
}

void safe(char *cstr)
{
	char *chrs = "0123456789ABCDEFabcdef.:";
	int x, y, l = strlen(cstr), m = strlen(chrs), flag;
	for (x = 0; x < l; ++x)
	{
		flag = 0;
		for (y = 0; y < m; ++y)
		{
			if (chrs[y] == cstr[x])
			{
				flag = 1;
			}
		}
		if (flag == 0)
		{
			cstr[x] = '0';
		}
	}
}

unsigned long ipvf(char *addr)
{
	unsigned long i = 0;
	char *p = NULL, *a = strdup(addr), *t = a;
	while (1)
	{
		p = strchr(a, '.');
		if (p != NULL) { *p = '\0'; }
		i = ((i << 8) + atoi(a));
		a = (p + 1);
		if (p == NULL) { break; }
	}
	free(t);
	return i;
}

int sign(char *pmsg, int size, unsigned long pres, char *skey)
{
	int x;
	char hash[SHA256_LENGTH*4];
	unsigned char hout[SHA256_LENGTH];
	SHA256_CTX hobj;
	
	snprintf(&(pmsg[strlen(pmsg)]), (size / 4) * sizeof(char), " %ld %s", pres, skey);
	
	SHA256_INIT(&hobj);
	SHA256_UPDATE(&hobj, (unsigned char *)pmsg, strlen(pmsg));
	SHA256_FINAL(&hobj, hout);
	for (x = 0; x < SHA256_LENGTH; ++x)
	{
		sprintf(&(hash[x*2]), "%02x", hout[x]);
	}
	hash[SHA256_LENGTH*2] = '\0';
	
	char *rptr = strrchr(pmsg, ' ');
	++rptr;
	strcpy(rptr, hash);
	rptr[SHA256_LENGTH*2] = '\0';
	
	return 0;
}

int vrfy(char *pmsg, int size, char *skey, char *sign, unsigned long rate, unsigned long pres, unsigned long last)
{
	int x;
	char hash[SHA256_LENGTH*4];
	unsigned char hout[SHA256_LENGTH];
	SHA256_CTX hobj;
	
	snprintf(&(pmsg[strlen(pmsg)]), (size / 4) * sizeof(char), " %ld %s", pres, skey);
	
	SHA256_INIT(&hobj);
	SHA256_UPDATE(&hobj, (unsigned char *)pmsg, strlen(pmsg));
	SHA256_FINAL(&hobj, hout);
	for (x = 0; x < SHA256_LENGTH; ++x)
	{
		sprintf(&(hash[x*2]), "%02x", hout[x]);
	}
	hash[SHA256_LENGTH*2] = '\0';
	
	if (strcmp(hash, sign) != 0) { return -1; }
	if ((time(NULL) - rate) < 3) { return -1; }
	if (pres <= last) { return -1; }
	
	return 0;
}

int find(infodata *objs, int l, char *i)
{
	int x;
	for (x = 0; x < l; ++x)
	{
		if (objs[x].i == NULL) { objs[x].i = strdup(i); return x; }
		if (strcmp(objs[x].i, i) == 0) { return x; }
	}
	return -1;
}

int uniq(infodata *objs, int l, int i, unsigned long a)
{
	int x;
	for (x = 0; x < l; ++x)
	{
		if ((x != i) && (objs[x].a == a))
		{
			return x;
		}
	}
	objs[i].a = a;
	return -1;
}

char *gnet(char *intf, char mode)
{
	char *info = "ifconfig '%s' | sed -e 's/HWaddr/ether/g' -e 's/addr://g' -e 's/Bcast:/broadcast /g' | %s > /tmp/arp.net";
	char *inet = "grep -i 'inet ' | sed -e 's/^.*inet[ ]*\\([^ ]*\\).*$/\\1/g'";
	char *maca = "grep -i 'ether ' | sed -e 's/^.*ether[ ]*\\([^ ]*\\).*$/\\1/g'";
	char *brod = "grep -i 'broadcast ' | sed -e 's/^.*broadcast[ ]*\\([^ ]*\\).*$/\\1/g'";
	char comd[2048];
	FILE *fobj;
	
	bzero(comd, 2048 * sizeof(char));
	
	if (mode == 'i') { snprintf(comd, 1024 * sizeof(char), info, intf, inet); }
	if (mode == 'm') { snprintf(comd, 1024 * sizeof(char), info, intf, maca); }
	if (mode == 'b') { snprintf(comd, 1024 * sizeof(char), info, intf, brod); }
	
	system(comd);
	
	fobj = fopen("/tmp/arp.net", "r");
	bzero(comd, 2048 * sizeof(char));
	fgets(comd, 1024 * sizeof(char), fobj);
	strp(comd, strlen(comd));
	fclose(fobj);
	
	return strdup(comd);
}

void serv(char **args)
{
	/* note: 256 ip address range limit */
	
	int x, y, rlen, sock, bron = 1;
	unsigned long aadr = ipvf(args[4]), badr = ipvf(args[5]), secs;
	char *iadr = gnet(args[2], 'i'), *madr = gnet(args[2], 'm');
	char pass[2048], mesg[2048], temp[2048], sarp[2048];
	infodata last[256];
	FILE *fobj;
	socklen_t slen;
	struct sockaddr_in sobj, cobj;
	
	for (x = 0; x < 256; ++x)
	{
		last[x].i = NULL; last[x].a = 0;
		last[x].t = time(NULL); last[x].l = 0;
	}
	
	sock = socket(AF_INET, SOCK_DGRAM, 0);
	setsockopt(sock, SOL_SOCKET, SO_BROADCAST, &bron, sizeof(bron));
	
	bzero(&sobj, sizeof(sobj));
	sobj.sin_family = AF_INET;
	sobj.sin_addr.s_addr = htonl(INADDR_ANY);
	sobj.sin_port = htons(31337);
	
	bind(sock, (struct sockaddr *)&sobj, sizeof(sobj));
	
	while (1)
	{
		slen = sizeof(cobj);
		rlen = recvfrom(sock, mesg, 1024 * sizeof(char), 0, (struct sockaddr *)&cobj, &slen);
		strp(mesg, rlen);
		
		char *hptr = strrchr(mesg, ' '); if (hptr == NULL) { continue; }
		*hptr = '\0'; ++hptr;
		char *tptr = strrchr(mesg, ' '); if (tptr == NULL) { continue; }
		*tptr = '\0'; ++tptr;
		
		char *mptr = strrchr(mesg, ' '); if (mptr == NULL) { continue; }
		*mptr = '\0'; ++mptr;
		char *iptr = mesg;
		
		fobj = fopen(args[3], "r");
		while (1)
		{
			bzero(pass, 2048 * sizeof(char));
			if (fgets(pass, 1024 * sizeof(char), fobj) == NULL) { break; }
			
			/* note: passwords can not repeat or contain quotes */
			
			if (strstr(pass, "Cleartext-Password") == NULL) { continue; }
			char *aptr = strchr(pass, '"'); if (aptr == NULL) { continue; }
			++aptr;
			char *bptr = strchr(aptr, '"'); if (bptr == NULL) { continue; }
			*bptr = '\0';
			
			y = find(last, 256, aptr);
			if (y < 0) { continue; }
			
			bzero(temp, 2048 * sizeof(char));
			snprintf(temp, 1024 * sizeof(char), "%s %s", iptr, mptr);
			secs = atoi(tptr);
			
			if (vrfy(temp, 2048, aptr, hptr, last[y].t, secs, last[y].l) == 0)
			{
				last[y].t = time(NULL); last[y].l = secs;
				safe(iptr); safe(mptr);
				
				if (uniq(last, 256, y, ipvf(iptr)) < 0)
				{
					if ((aadr <= last[y].a) && (last[y].a <= badr))
					{
						bzero(sarp, 2048 * sizeof(char));
						snprintf(sarp, 1024 * sizeof(char), "arp -d '%s'", iptr);
						printf("exec=[%s]\n", sarp);
						system(sarp);
						
						bzero(sarp, 2048 * sizeof(char));
						snprintf(sarp, 1024 * sizeof(char), "arp -s '%s' '%s'", iptr, mptr);
						printf("exec=[%s]\n", sarp);
						system(sarp);
						
						bzero(sarp, 2048 * sizeof(char));
						snprintf(sarp, 1024 * sizeof(char), "%s %s", iadr, madr);
						sign(sarp, 2048, secs + 1, aptr);
						
						sendto(sock, sarp, strlen(sarp) * sizeof(char), 0, (struct sockaddr *)&cobj, sizeof(cobj));
						printf("sent=[%s]\n", sarp);
					}
					
					else
					{
						printf("erro=[range: %ld <= %ld <= %ld]\n", aadr, last[y].a, badr);
					}
				}
				
				else
				{
					printf("erro=[uniq: %ld]\n", ipvf(iptr));
				}
			}
			
			else
			{
				temp[30] = '\0';
				//printf("erro=[vrfy: (%s...) (%s) (%ld) (%ld)]\n", temp, hptr, secs, last[y].l);
			}
		}
		fclose(fobj);
	}
}

void ahnd(int sig)
{
	printf("No mesg\n");
}

void clnt(char **args)
{
	int sock, bron = 1;
	unsigned long tips, secs;
	char pass[2048], mesg[2048], temp[2048], sarp[2048];
	socklen_t slen;
	struct sockaddr_in cobj;
	
	//char *brod = "255.255.255.255";
	//signal(SIGALRM, ahnd);
	
	struct sigaction sact = { .sa_handler = ahnd, .sa_flags = 0 };
	sigaction(SIGALRM, &sact, NULL);
	
	bzero(pass, 2048 * sizeof(char));
	fgets(pass, 1024, stdin);
	strp(pass, strlen(pass));
	
	while (1)
	{
		char *iadr = gnet(args[2], 'i'), *madr = gnet(args[2], 'm'), *badr = gnet(args[2], 'b');
		
		sock = socket(AF_INET, SOCK_DGRAM, 0);
		setsockopt(sock, SOL_SOCKET, SO_BROADCAST, &bron, sizeof(bron));
		
		cobj.sin_family = AF_INET;
		cobj.sin_port = htons(31337);
		inet_aton(badr, (struct in_addr *)&cobj.sin_addr.s_addr);
		
		bzero(mesg, 2048 * sizeof(char));
		snprintf(mesg, 1024 * sizeof(char), "%s %s", iadr, madr);
		
		secs = time(NULL);
		sign(mesg, 2048, secs, pass);
		
		sendto(sock, mesg, strlen(mesg) * sizeof(char), 0, (struct sockaddr*)&cobj, sizeof(cobj));
		printf("Sent mesg %s with socket %d to %s\n", mesg, sock, badr);
		
		slen = sizeof(cobj);
		bzero(mesg, 2048 * sizeof(char));
		alarm(1);
		recvfrom(sock, mesg, 1024 * sizeof(char), 0, (struct sockaddr *)&cobj, &slen);
		alarm(0);
		strp(mesg, strlen(mesg));
		
		char *hptr = strrchr(mesg, ' '); if (hptr != NULL) { *hptr = '\0'; ++hptr; }
		char *tptr = strrchr(mesg, ' '); if (tptr != NULL) { *tptr = '\0'; ++tptr; }
		
		char *mptr = strrchr(mesg, ' ');
		char *iptr = mesg;
		
		if ((hptr != NULL) && (tptr != NULL) && (mptr != NULL))
		{
			bzero(temp, 2048 * sizeof(char));
			strcpy(temp, mesg);
			
			tips = atoi(tptr);
			*mptr = '\0'; ++mptr;
			
			if (vrfy(temp, 2048, pass, hptr, time(NULL) - 5, tips, secs) == 0)
			{
				safe(iptr); safe(mptr);
				
				bzero(sarp, 2048 * sizeof(char));
				snprintf(sarp, 1024 * sizeof(char), "arp -d '%s'", iptr);
				printf("exec=[%s]\n", sarp);
				system(sarp);
				
				bzero(sarp, 2048 * sizeof(char));
				snprintf(sarp, 1024 * sizeof(char), "arp -s '%s' '%s'", iptr, mptr);
				printf("exec=[%s]\n", sarp);
				system(sarp);
			}
			
			else
			{
				temp[30] = '\0';
				//printf("erro=[vrfy: (%s...) (%s) (%s) (%ld) (%ld)]\n", temp, pass, hptr, tips, secs);
			}
		}
		
		close(sock);
		//break;
		sleep(5);
	}
}

int main(int argc, char **argv)
{
	if (strcmp(argv[1], "s") == 0)
	{
		serv(argv);
	}
	
	if (strcmp(argv[1], "c") == 0)
	{
		clnt(argv);
	}
	
	return 0;
}

sha256.c

#define SHA256_LENGTH 32

#define uchar unsigned char // 8-bit byte
#define uint unsigned int // 32-bit word

// DBL_INT_ADD treats two unsigned ints a and b as one 64-bit integer and adds c to it
#define DBL_INT_ADD(a,b,c) if (a > 0xffffffff - (c)) ++b; a += c;
#define ROTLEFT(a,b) (((a) << (b)) | ((a) >> (32-(b))))
#define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b))))

#define CH(x,y,z) (((x) & (y)) ^ (~(x) & (z)))
#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
#define EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))
#define EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))
#define SIG0(x) (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3))
#define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10))

typedef struct {
   uchar data[64];
   uint datalen;
   uint bitlen[2];
   uint state[8];
} SHA256_CTX;

uint k[64] = {
   0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
   0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
   0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
   0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
   0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
   0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
   0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
   0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
};

void SHA256_TRANSFORM(SHA256_CTX *ctx, uchar data[])
{
   uint a,b,c,d,e,f,g,h,i,j,t1,t2,m[64];

   for (i=0,j=0; i < 16; ++i, j += 4)
      m[i] = (data[j] << 24) | (data[j+1] << 16) | (data[j+2] << 8) | (data[j+3]);
   for ( ; i < 64; ++i)
      m[i] = SIG1(m[i-2]) + m[i-7] + SIG0(m[i-15]) + m[i-16];

   a = ctx->state[0];
   b = ctx->state[1];
   c = ctx->state[2];
   d = ctx->state[3];
   e = ctx->state[4];
   f = ctx->state[5];
   g = ctx->state[6];
   h = ctx->state[7];

   for (i = 0; i < 64; ++i) {
      t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];
      t2 = EP0(a) + MAJ(a,b,c);
      h = g;
      g = f;
      f = e;
      e = d + t1;
      d = c;
      c = b;
      b = a;
      a = t1 + t2;
   }

   ctx->state[0] += a;
   ctx->state[1] += b;
   ctx->state[2] += c;
   ctx->state[3] += d;
   ctx->state[4] += e;
   ctx->state[5] += f;
   ctx->state[6] += g;
   ctx->state[7] += h;
}

void SHA256_INIT(SHA256_CTX *ctx)
{
   ctx->datalen = 0;
   ctx->bitlen[0] = 0;
   ctx->bitlen[1] = 0;
   ctx->state[0] = 0x6a09e667;
   ctx->state[1] = 0xbb67ae85;
   ctx->state[2] = 0x3c6ef372;
   ctx->state[3] = 0xa54ff53a;
   ctx->state[4] = 0x510e527f;
   ctx->state[5] = 0x9b05688c;
   ctx->state[6] = 0x1f83d9ab;
   ctx->state[7] = 0x5be0cd19;
}

void SHA256_UPDATE(SHA256_CTX *ctx, uchar data[], uint len)
{
   uint i;

   for (i=0; i < len; ++i) {
      ctx->data[ctx->datalen] = data[i];
      ctx->datalen++;
      if (ctx->datalen == 64) {
         SHA256_TRANSFORM(ctx,ctx->data);
         DBL_INT_ADD(ctx->bitlen[0],ctx->bitlen[1],512);
         ctx->datalen = 0;
      }
   }
}

void SHA256_FINAL(SHA256_CTX *ctx, uchar hash[])
{
   uint i;

   i = ctx->datalen;

   // Pad whatever data is left in the buffer.
   if (ctx->datalen < 56) {
      ctx->data[i++] = 0x80;
      while (i < 56)
         ctx->data[i++] = 0x00;
   }
   else {
      ctx->data[i++] = 0x80;
      while (i < 64)
         ctx->data[i++] = 0x00;
      SHA256_TRANSFORM(ctx,ctx->data);
      memset(ctx->data,0,56);
   }

   // Append to the padding the total message's length in bits and transform.
   DBL_INT_ADD(ctx->bitlen[0],ctx->bitlen[1],ctx->datalen * 8);
   ctx->data[63] = ctx->bitlen[0];
   ctx->data[62] = ctx->bitlen[0] >> 8;
   ctx->data[61] = ctx->bitlen[0] >> 16;
   ctx->data[60] = ctx->bitlen[0] >> 24;
   ctx->data[59] = ctx->bitlen[1];
   ctx->data[58] = ctx->bitlen[1] >> 8;
   ctx->data[57] = ctx->bitlen[1] >> 16;
   ctx->data[56] = ctx->bitlen[1] >> 24;
   SHA256_TRANSFORM(ctx,ctx->data);

   // Since this implementation uses little endian byte ordering and SHA uses big endian,
   // reverse all the bytes when copying the final state to the output hash.
   for (i=0; i < 4; ++i) {
      hash[i]    = (ctx->state[0] >> (24-i*8)) & 0x000000ff;
      hash[i+4]  = (ctx->state[1] >> (24-i*8)) & 0x000000ff;
      hash[i+8]  = (ctx->state[2] >> (24-i*8)) & 0x000000ff;
      hash[i+12] = (ctx->state[3] >> (24-i*8)) & 0x000000ff;
      hash[i+16] = (ctx->state[4] >> (24-i*8)) & 0x000000ff;
      hash[i+20] = (ctx->state[5] >> (24-i*8)) & 0x000000ff;
      hash[i+24] = (ctx->state[6] >> (24-i*8)) & 0x000000ff;
      hash[i+28] = (ctx->state[7] >> (24-i*8)) & 0x000000ff;
   }
}

Well, I just relocated to California to start a new career for a well known & respected tech company. Everything so far has been great (weather, people, food, work) except for one thing, the cost of living! I thought people were kinda joking when they warned me but it’s absolutely insane out here. If you take the Americana Apartments for example, they quoted their lowest 1 bedroom for $2480 per month. The representative said that in order to qualify, you must earn 3x that amount in monthly salary (before taxes of course). So let’s see, the minimum yearly wage must be at least, $2480 * 3x * 12m = $89,280! (let’s call it 90 even with utilities, electric, water, garbage, insurance, etc). In addition, in order to reserve a place, you must put down: first ($2480), last ($2480), deposit ($500), utilities ($125), insurance ($20), a bed, internet, etc… which comes out to be over $5,600 of initial payment.

I’m finding it really hard to find places which aren’t built like resorts (pools, hot tubs, lounge chairs, ping pong tables, pool tables, rec rooms, common areas, bars, etc.) and places which aren’t in rough areas, old buildings, poorly maintained, etc. There doesn’t seem to be much middle ground available unless you spend your whole day looking around at every possible option.

Anyway, I guess at the end of the day I’m lucky to be where I am but yeah, it’s kinda crazy out here to be honest! Hopefully I can get back to some useful open source coding again once I get settled in. 🙂

Don’t trust web based secure email, one cannot verify if the delivery of a web page has been modified or not given today’s tools. A powerful adversary could MITM an HTTPS connection with a valid, signed CA cert and there are no tools today which can provably validate that the integrity of a web page has not been modified since it left the server and entered your browser. I’m trying to work on a client based solution compatible with Gmail but it’s taking me time, I keep getting distracted by other things going on. Anyway, here’s a random post in case I need a fast stream cipher similar to ARC4 but with better security.

ChaCha Python

import hashlib
class chacha:
	def p(self, a, i):
		return ((ord(a[i]) << 24) + (ord(a[i+1]) << 16) + (ord(a[i+2]) << 8) + ord(a[i+3]))
	def r(self, a, n):
		return ((a << n) & 0xffffffff) | (a >> (32 - n))
	def z(self, a, b):
		return ((a + b) & 0xffffffff)
	def u(self, m, x, k, y):
		c = ""
		for i in range(0, 4):
			c += chr(ord(m[x+i]) ^ ((k[y] >> (i*8)) & 0xff))
		return c
	def __init__(self, k, r=20):
		self.pt = [0x61707865, 0x3120646e, 0x79622d36, 0x6b206574]
		self.ps = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
		self.rs = r
		l = len(k)
		if (l == 16):
			self.skey = [
				self.pt[0], self.pt[1], self.pt[2], self.pt[3],
				self.p(k, 0), self.p(k, 4), self.p(k, 8), self.p(k, 12),
				self.p(k, 0), self.p(k, 4), self.p(k, 8), self.p(k, 12),
				0x0, 0x0, 0x0, 0x0
			]
		if (l == 32):
			self.skey = [
				self.ps[0], self.ps[1], self.ps[2], self.ps[3],
				self.p(k,  0), self.p(k,  4), self.p(k,  8), self.p(k, 12),
				self.p(k, 16), self.p(k, 20), self.p(k, 24), self.p(k, 28),
				0x0, 0x0, 0x0, 0x0
			]
	def qrrd(self, x, a, b, c, d):
		x[a] = self.z(x[a], x[b]); x[d] = (x[d] ^ x[a]); x[d] = self.r(x[d], 16)
		x[c] = self.z(x[c], x[d]); x[b] = (x[b] ^ x[c]); x[b] = self.r(x[b], 12)
		x[a] = self.z(x[a], x[b]); x[d] = (x[d] ^ x[a]); x[d] = self.r(x[d],  8)
		x[c] = self.z(x[c], x[d]); x[b] = (x[b] ^ x[c]); x[b] = self.r(x[b],  7)
		return x
	def core(self):
		x = self.skey[:]
		for r in range(0, self.rs / 2):
			x = self.qrrd(x, 0, 4,  8, 12)
			x = self.qrrd(x, 1, 5,  9, 13)
			x = self.qrrd(x, 2, 6, 10, 14)
			x = self.qrrd(x, 3, 7, 11, 15)
			# rows vs cols
			x = self.qrrd(x, 0, 5, 10, 15)
			x = self.qrrd(x, 1, 6, 11, 12)
			x = self.qrrd(x, 2, 7,  8, 13)
			x = self.qrrd(x, 3, 4,  9, 14)
		for i in range(0, 16):
			x[i] = self.z(x[i], self.skey[i])
		return x
	def cipher(self, m):
		while ((len(m) % 64) != 0):
			m += chr(0)
		i = 0; l = len(m)
		o = ""
		while ((i + 63) < l):
			s = self.core()
			j = 0
			while ((j + 3) < 64):
				o += self.u(m, j, s, j / 4)
				j += 4
			self.skey[12] = self.z(self.skey[12], 1)
			if (self.skey[12] == 0):
				self.skey[13] += 1
			i += 64
		return o
c = chacha(hashlib.sha256("abc").digest())
e = c.cipher("def");print("",e)
c = chacha(hashlib.sha256("abc").digest())
d = c.cipher(e);print("",d.strip("\0"))

Edit: I need to verify the math on the code below and optimize it as much as possible!

The message being encrypted by the public key and decrypted by the private key is [71, 73], as you can see below, in both Python and JavaScript.

Output:

point=[31338, 27137639241784266545116051737587625422240160049866585375429726394143891718199] ((y^2)%p)=508712386423338 == curve(x)=508712386423338
pub=[53977350860898987307302427493695333251161207860469554940047122752933735592647, 26210366092361168208973994509836336790598036553932356811338803611050445452207]
& [1445723211146282456267893060679523547963682350054864882998693087748930328718927, 2685102703073507930430754637571136937637097240643254035250750702470189871650545]
mesg=[71, 73]
time=254 ms

JS:

<script src="jsbn.js"></script>
<script src="jsbn2.js"></script>
<script>
var c = new BigInteger("486662", 10);
var p = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564819949", 10);
var two = new BigInteger("2", 10);
var three = new BigInteger("3", 10);

function safe_sub(a, p)
{
	if (a.compareTo(BigInteger.ZERO) < 0)
	{
		var r = a.abs().divide(p);
		a = a.add(r.multiply(p));
		if (a.compareTo(BigInteger.ZERO) < 0)
		{
			a = a.add(p);
		}
	}
	return a;
}

function point_add(q, r, p)
{
	var ys = safe_sub(q[1].subtract(r[1]), p);
	var xs = safe_sub(q[0].subtract(r[0]), p);
	var s = ys.multiply(xs.modInverse(p)).mod(p);
	var rx = s.modPow(two, p);
	rx = safe_sub(rx.subtract(q[0]), p);
	rx = safe_sub(rx.subtract(r[0]), p);
	var rp = safe_sub(q[0].subtract(rx), p);
	var ry = safe_sub(s.multiply(rp).mod(p).subtract(q[1]), p);
	return [rx, ry];
}

function point_dub(a, q, p)
{
	var ttt = three.multiply(q[0].modPow(two, p)).mod(p);
	var tt = two.multiply(q[1]).mod(p);
	var s = ttt.add(a).multiply(tt.modInverse(p)).mod(p);
	tt = two.multiply(q[0]).mod(p);
	var rx = safe_sub(s.modPow(two, p).subtract(tt), p);
	var rp = safe_sub(q[0].subtract(rx), p);
	var ry = safe_sub(s.multiply(rp).mod(p).subtract(q[1]), p);
	return [rx, ry];
}

function point_mul(n, q, p)
{
	//if(this.isInfinity()) return this;
	//if(k.signum() == 0) return this.curve.getInfinity();
	
	var e = n;
	var h = e.multiply(three);
	
	var neg = [q[0], safe_sub(q[1].negate(), p)];
	var R = q;
	
	var i;
	for (i = (h.bitLength() - 2); i > 0; --i)
	{
		R = point_dub(BigInteger.ONE, R, p);
		
		var hBit = h.testBit(i);
		var eBit = e.testBit(i);
		
		if (hBit != eBit)
		{
			R = point_add(hBit ? q : neg, R, p);
		}
	}
	
	return R;
}

function ord_r(r, n)
{
	var k = three;
	while (1)
	{
		if (n.modPow(k, r).equals(BigInteger.ONE))
		{
			return k;
		}
		k = k.add(BigInteger.ONE);
	}
}

function ifrexp(x)
{
	var e = BigInteger.ZERO;
	while (x.mod(two).equals(BigInteger.ZERO))
	{
		x = x.divide(two);
		e = e.add(BigInteger.ONE);
	}
	return [x, e];
}

function tonelli(a, p)
{
	var pmo = p.subtract(BigInteger.ONE);
	if (a.modPow(pmo.divide(two), p).equals(pmo))
	{
		return -1;
	}
	var t = ifrexp(pmo);
	var s = t[0], e = t[1];
	var n = two;
	while (n.compareTo(p) < 0)
	{
		if (n.modPow(pmo.divide(two), p).equals(pmo))
		{
			break;
		}
		n = n.add(BigInteger.ONE);
	}
	var x = a.modPow(s.add(BigInteger.ONE).divide(two), p);
	var b = a.modPow(s, p);
	var g = n.modPow(s, p);
	var r = e;
	while (1)
	{
		var m = BigInteger.ZERO;
		while (m.compareTo(r) < 0)
		{
			if (ord_r(p, b).equals(two.pow(m)))
			{
				break;
			}
			if (m.add(BigInteger.ONE).equals(r))
			{
				break;
			}
			m = m.add(BigInteger.ONE);
		}
		if (m.equals(BigInteger.ZERO))
		{
			return x;
		}
		var pmi = two.pow(r.subtract(m).subtract(BigInteger.ONE));
		x = x.multiply(g.modPow(pmi, p)).mod(p);
		pmi = two.pow(r.subtract(m));
		g = g.modPow(pmi, p);
		b = b.multiply(g).mod(p);
		if (b.equals(BigInteger.ONE))
		{
			return x;
		}
		r = m;
	}
	return -1;
}

function curve_25519(x, p)
{
	var y2 = x.modPow(three, p).add(c.multiply(x.modPow(two, p))).add(x).mod(p);
	return tonelli(y2, p);
}

var i = new BigInteger("31337", 10);
var pnt = null
while (pnt == null)
{
	var q = [i, curve_25519(i, p)];
	if (q[1] == -1)
	{
		i = i.add(BigInteger.ONE);
		continue;
	}
	var x = q[0].modPow(three, p).add(c.multiply(q[0].modPow(two, p))).add(q[0]).mod(p);
	var y = q[1].modPow(two, p);
	if (x.equals(y))
	{
		pnt = q;
		document.write("point=["+pnt[0].toString(10)+", "+pnt[1].toString(10)+"] ((y^2)%p)="+y.toString(10)+" == "+"curve(x)="+x.toString(10)+"<br>");
	}
	i = i.add(BigInteger.ONE);
}

var m = new BigInteger("71", 10);
var n = new BigInteger("73", 10);

var nta = new Date().getTime();

var a = new BigInteger("23002347587565544268625339214141417360725798840824195817183950850507406831337", 10);
var aG = point_mul(a, pnt, p);

var b = new BigInteger("33951982198225404751798578318443600923434009233142787987410481710685782131337", 10);
var bG = point_mul(b, pnt, p);
var baG = point_mul(b, aG, p);

var mbaG = [m.multiply(baG[0]), n.multiply(baG[1])];

var abG = point_mul(a, bG, p);

var ntb = new Date().getTime();

document.write("pub=["+bG[0]+", "+bG[1]+"]<br> & ["+mbaG[0]+", "+mbaG[1]+"]<br>"+"mesg=["+mbaG[0].divide(abG[0]).toString(10)+", "+mbaG[1].divide(abG[1]).toString(10)+"]<br>"+"time="+(ntb-nta)+" ms<br>");
</script>

Output:

('point', [31338, 27137639241784266545116051737587625422240160049866585375429726394143891718199L], 'y^2%p=', 508712386423338L, '==', 'curve(x)', 508712386423338L)
pub=[53977350860898987307302427493695333251161207860469554940047122752933735592647L, 26210366092361168208973994509836336790598036553932356811338803611050445452207L]
 & [1445723211146282456267893060679523547963682350054864882998693087748930328718927L, 2685102703073507930430754637571136937637097240643254035250750702470189871650545L]
mesg=[71, 73]
time=145.143032074 ms

Py:

import time

p = (pow(2, 255) - 19)

def egcd(a, b):
	if (a == 0):
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - (b / a) * y, y)

def inv_mod(a, m):
	(g, x, y) = egcd(a, m)
	if (g != 1):
		return -1
	else:
		return (x % m)

def pow_mod(b, e, m):
	r = 1
	b = (b % m)
	while (e > 0):
		if ((e % 2) == 1):
			r = ((r * b) % m)
		e = (e / 2)
		b = ((b * b) % m)
	return r

def safe_sub(a, p):
	if (a < 0):
		a += ((abs(a) / p) * p)
		if (a < 0):
			a += p
	return a

def point_add(q, r, p):
	ys = safe_sub(q[1] - r[1], p)
	xs = safe_sub(q[0] - r[0], p)
	s = ((ys * inv_mod(xs, p)) % p)
	rx = pow_mod(s, 2, p)
	rx = safe_sub(rx - q[0], p)
	rx = safe_sub(rx - r[0], p)
	rp = safe_sub(q[0] - rx, p)
	ry = safe_sub(((s * rp) % p) - q[1], p)
	return [rx, ry]

def point_dub(a, q, p):
	ttt = ((3 * pow_mod(q[0], 2, p)) % p)
	tt = ((2 * q[1]) % p)
	s = (((ttt + a) * inv_mod(tt, p)) % p)
	tt = ((2 * q[0]) % p)
	rx = safe_sub(pow_mod(s, 2, p) - tt, p)
	rp = safe_sub(q[0] - rx, p)
	ry = safe_sub(((s * rp) % p) - q[1], p)
	return [rx, ry]

def zpoint_mul(n, q, p):
	r = q; m = 1
	h = [[m, r]]; l = 1
	while (m < n):
		t = (m * 2)
		if (t <= n):
			r = point_dub(1, r, p); m = t
			h.append([m, r]); l += 1
		else:
			x = (l - 1)
			while (x > -1):
				while (m < n):
					t = (m + h[x][0])
					if (t <= n):
						r = point_add(h[x][1], r, p); m = t
					else:
						break
				x -= 1
	return r

def bitleng(a):
	b = 0
	while (a > 0):
		a = (a / 2)
		b += 1
	return b

def testbit(a, b):
	if ((a & pow(2, b)) > 0):
		return 1
	return 0

def point_mul(n, q, p):
	#if(this.isInfinity()) return this;
	#if(k.signum() == 0) return this.curve.getInfinity();
	
	e = n
	h = (e * 3)
	
	neg = [q[0], safe_sub(-1 * q[1], p)]
	R = q
	
	i = (bitleng(h) - 2)
	while (i > 0):
		R = point_dub(1, R, p)
		
		hBit = testbit(h, i)
		eBit = testbit(e, i)
		
		if (hBit != eBit):
			if (hBit):
				R = point_add(q, R, p)
			else:
				R = point_add(neg, R, p)
		
		i -= 1
	
	return R

def ord_r(r, n):
	k = 3
	while (1):
		if (pow_mod(n, k, r) == 1):
			return k
		k += 1

def ifrexp(x):
	e = 0
	while ((x % 2) == 0):
		x /= 2
		e += 1
	return (x, e)

def tonelli(a, p):
	if (pow_mod(a, (p - 1) / 2, p) == (p - 1)):
		raise ValueError("no sqrt possible")
	(s, e) = ifrexp(p - 1)
	n = 2
	while (n < p):
		if (pow_mod(n, (p - 1) / 2, p) == (p - 1)):
			break
		n += 1
	x = pow_mod(a, (s + 1) / 2, p)
	b = pow_mod(a, s, p)
	g = pow_mod(n, s, p)
	r = e
	while (1):
		m = 0
		while (m < r):
			if (ord_r(p, b) == pow(2, m)):
				break
			if ((m + 1) == r):
				break
			m += 1
		if (m == 0):
			return x
		x = ((x * pow_mod(g, pow(2, (r - m - 1)), p)) % p)
		g = pow_mod(g, pow(2, (r - m)), p)
		b = ((b * g) % p)
		if (b == 1):
			return x
		r = m
	return -1

def curve_25519(x, p):
	y2 = ((pow_mod(x, 3, p) + (486662 * pow_mod(x, 2, p)) + x) % p)
	return tonelli(y2, p)

i = 31337
pnt = None
while (pnt == None):
	try:
		q = [i, curve_25519(i, p)]
	except:
		i += 1
		continue
	x = ((pow_mod(q[0], 3, p) + (486662 * pow_mod(q[0], 2, p)) + q[0]) % p)
	y = pow_mod(q[1], 2, p)
	if (x == y):
		print("point",q,"y^2%p=",y,"==","curve(x)",x)
		pnt = q
	i += 1

m = 71; n = 73

x = time.time()

a = 23002347587565544268625339214141417360725798840824195817183950850507406831337
aG = point_mul(a, pnt, p)

b = 33951982198225404751798578318443600923434009233142787987410481710685782131337
bG = point_mul(b, pnt, p)
baG = point_mul(b, aG, p)

mbaG = [m * baG[0], n * baG[1]]

abG = point_mul(a, bG, p)

y = time.time()

print("pub=%s\n & %s\nmesg=[%d, %d]\ntime=%s ms" % (bG, mbaG, mbaG[0] / abG[0], mbaG[1] / abG[1], (y - x) * 1000))

So I’ve recently started a new, open-source project called S-Mail. It’s is an attempt to create a standard email service (based on standard postfix/SMTP) but also provide a web front end for secure email delivery. Upon joining, a 2048 bit RSA key pair is generated (via JavaScript) and the private key is encrypted with AES-256-CBC with the SHA256 hash of your password. The server stores your public key, a triple SHA256 hash of your password (so it doesn’t have your encryption key), and your encrypted private key. When an external email is received, it is encrypted with your public key and stored only in that format. When sending a local email, the server sends the recipient’s public key to you so that you can encrypt it locally first before sending it. You can also verify the key identities of the recipients by verifying the little word phrases which summarize your public key.

This service is really lacking features as it is the most basic start of a project possible but I’m attempting to at least develop a basic framework that people could theoretically use to exchange secure messages without having to exchange asymmetric keys. The “key” to making this system work includes choosing a strong passphrase to begin with and verifying a recipient’s key id.

The source code: Fossjon GitHub S-Mail

Below are some screenshots of the service working:

Joining

Login

Empty inbox

External SMTP Receive

Inbox Receive

External SMTP Read

External SMTP Send

Reading the external email

Internal SMTP Send

Internal SMTP Read

Overview:

1. Get the sqlite3 command & test the radius login locally to create the DB & OTP
2. Insert a row into the “server” table with the @gmail.com login/pass of the sending email address
3. Insert a row into the “login” table with the Wi-Fi login username, $salt$<wpa-pbkdf2(salt,password)>, & email/sms address

That’s it, now you have one time pads being sent to your phone for your home Wi-Fi enterprise login and you simply append those 6 digit numbers to the end of your password. Make sure to turn off your Wi-Fi password saving as well.

Source code can be found here:   [GIT Repo]

vim /etc/freeradius/sites-{available,enabled}/{default,inner-tunnel}

...
authorize {
    ...
    update control {
        Auth-Type := `/usr/bin/python /opt/freeradius/freeauth.py 86400 %{User-Name} %{User-Password}`
    }
    ...
}
...

vim /opt/freeradius/freeauth.py – needs correct freeradius permissions

#!/usr/bin/python

import crypt
import hashlib
import hmac
import os
import random
import re
import smtplib
import sqlite3
import string
import sys
import time

def sqloexec(sqloobjc, sqlocomd):
	try:
		sqloobjc.execute(sqlocomd)
	except:
		pass

def cleanstr(inputstr):
	outpstri = ""
	charlist = (string.digits + string.uppercase + string.lowercase)
	for inputchr in inputstr:
		if (inputchr in charlist):
			outpstri += inputchr
	return outpstri

def pbkdfsha(s, p):
	i = 1; l = ((256 / 8) * 2); d = ""
	while (len(d) < l):
		c = 0; rounds = 4096; f = ""
		lasthmac = (s + chr((i >> 24) & 0xff) + chr((i >> 16) & 0xff) + chr((i >> 8) & 0xff) + chr((i >> 0) & 0xff))
		while (c < rounds):
			u = hmac.new(p, lasthmac, hashlib.sha1).digest()
			lasthmac = u
			t = ""
			for x in range(0, len(u)):
				if (x >= len(f)):
					f += chr(0)
				t += chr(ord(f[x]) ^ ord(u[x]))
			f = t
			c += 1
		for j in f:
			q = ""
			if (ord(j) < 0x10):
				q = "0"
			if (len(d) < l):
				h = hex(ord(j))
				d += (q + h[2:])
		i += 1
	return d

denystri = "Reject"
authstri = "Accept"

mailuser = ""
mailpass = ""

expstime = int(sys.argv[1])
username = cleanstr(sys.argv[2])
userpass = sys.argv[3]
usercode = ""
regxobjc = re.match("^(.*[^0-9])([0-9]+)$", userpass)
if (regxobjc):
	userpass = str(regxobjc.group(1))
	usercode = str(regxobjc.group(2))
usermail = [""]
mailcode = ""

sqloconn = sqlite3.connect("/opt/freeradius/freeauth.db")
sqlocurs = sqloconn.cursor()

sqloexec(sqlocurs, "CREATE TABLE server (user TEXT, pass TEXT);")
sqloexec(sqlocurs, "CREATE TABLE login (user TEXT, pass TEXT, mail TEXT);")
sqloexec(sqlocurs, "CREATE TABLE token (loginuser TEXT, code TEXT, time INTEGER, exps INTEGER);")

for sqlorowo in sqlocurs.execute("SELECT * FROM server;"):
	mailuser = str(sqlorowo[0])
	mailpass = str(sqlorowo[1])

authflag = 0
for sqlorowo in sqlocurs.execute("SELECT * FROM login WHERE user = '" + username + "';"):
	sqlohash = str(sqlorowo[1])
	sqlomail = str(sqlorowo[2])
	sqloinfo = sqlohash.split("$")
	if (sqloinfo[2] == pbkdfsha(sqloinfo[1], userpass)):
		authflag = 1
		usermail[0] = sqlomail

if (authflag != 1):
	sqloconn.commit()
	sqloconn.close()
	sys.stdout.write(denystri);sys.exit(1)

prestime = int(time.time())
sqlocurs.execute("DELETE FROM token WHERE loginuser = '" + username + "' AND (" + str(prestime) + " - time) >= exps;")

authflag = 0
timelist = []
for sqlorowo in sqlocurs.execute("SELECT * FROM token WHERE loginuser = '" + username + "';"):
	sqlocode = str(sqlorowo[1])
	sqlotime = int(sqlorowo[2])
	if (sqlocode == usercode):
		authflag = 1
	timelist.append(sqlotime)
timelist.sort()

if (authflag == 1):
	sqloconn.commit()
	sqloconn.close()
	sys.stdout.write(authstri);sys.exit(0)

sendcode = 0
if (len(timelist) >= 1):
	if ((prestime - timelist[-1]) >= 60):
		sendcode = 1
else:
	sendcode = 1

if (sendcode == 1):
	for x in range(0, 6):
		mailcode += str(random.randint(0, 9))
	sqlocurs.execute("INSERT INTO token VALUES ('" + username + "', '" + mailcode + "', " + str(prestime) + ", " + str(expstime) + ");")

if ((mailuser != "") and (mailpass != "") and (usermail[0] != "") and (mailcode != "")):
	mailmesg = "\r\n".join([
		"From: " + mailuser,
		"To: " + usermail[0],
		"Subject: Code = " + mailcode,
		"",
		"OTP Auth Delivery"
	])
	
	server = smtplib.SMTP("smtp.gmail.com:587")
	server.ehlo()
	server.starttls()
	server.login(mailuser, mailpass)
	server.sendmail(mailuser, usermail, mailmesg)
	server.quit()

sqloconn.commit()
sqloconn.close()
sys.stdout.write(denystri);sys.exit(1)

…and!… a SSH PAM OTP too:

/*

gcc -fPIC -DPIC -shared -rdynamic -o sshdauth.so sshdauth.c
cp -fv sshdauth.so /lib/`uname -m`-linux-gnu/security/

vim /etc/pam.d/sshd
auth required sshdauth.so

vim /etc/ssh/sshd_config
UsePAM yes
UsePrivilegeSeparation no
PasswordAuthentication yes
ChallengeResponseAuthentication yes

*/

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

#include <security/pam_appl.h>
#include <security/pam_modules.h>

int pam_sm_setcred(pam_handle_t *pamh, int flags, int argc, const char *argv[]) { return PAM_SUCCESS; }

int pam_sm_authenticate(pam_handle_t *pamh, int flags, int argc, const char **argv)
{
	int pame = 0;
	const char *umsg = "Username: ", *pmsg = "Password: ", *cmsg = "Passcode: ";
	const char *user = NULL, *pass = NULL, *code = NULL;
	struct pam_conv *conv;
	struct pam_message mesg;
	struct pam_response *resp;
	const struct pam_message *msgp;
	
	int link[2];
	char data[96], auth[2048];
	pid_t pidn;
	
	/* pam setup */
	
	pame = pam_get_user(pamh, &user, NULL);
	if ((pame != PAM_SUCCESS) || (user == NULL))
	{
		return PAM_AUTH_ERR;
	}
	
	pame = pam_get_authtok(pamh, PAM_AUTHTOK, (const char **)&pass, NULL);
	if (pame != PAM_SUCCESS)
	{
		return PAM_AUTH_ERR;
	}
	
	if (fork() == 0)
	{
		execl("/usr/bin/python", "python", "/opt/freeradius/freeauth.py", "120", user, pass, NULL);
		exit(0);
	}
	
	wait(NULL);
	
	pame = pam_get_item(pamh, PAM_CONV, (const void **)&conv);
	if (pame != PAM_SUCCESS)
	{
		return PAM_AUTH_ERR;
	}
	//mesg.msg_style = PAM_PROMPT_ECHO_OFF;
	mesg.msg_style = PAM_PROMPT_ECHO_ON;
	mesg.msg = cmsg;
	msgp = &mesg;
	
	resp = NULL;
	pame = (*conv->conv)(1, &msgp, &resp, conv->appdata_ptr);
	if ((pame != PAM_SUCCESS) || (resp == NULL))
	{
		return PAM_AUTH_ERR;
	}
	code = resp->resp;
	
	/* auth check */
	
	if (pipe(link) == -1)
	{
		return PAM_AUTH_ERR;
	}
	
	pidn = fork();
	if (pidn == -1)
	{
		return PAM_AUTH_ERR;
	}
	
	if (pidn == 0)
	{
		dup2(link[1], STDOUT_FILENO);
		close(link[0]);
		bzero(auth, 2046 * sizeof(char));
		strncpy(auth, pass, 256);
		strncpy(auth + strlen(auth), code, 256);
		execl("/usr/bin/python", "python", "/opt/freeradius/freeauth.py", "120", user, auth, NULL);
		exit(0);
	}
	
	close(link[1]);
	bzero(data, 94 * sizeof(char));
	read(link[0], data, 92 * sizeof(char));
	wait(NULL);
	
	if (strcmp(data, "Accept") == 0)
	{
		return PAM_SUCCESS;
	}
	
	return PAM_AUTH_ERR;
}

So as you may or may not have known, I was recently let go without cause from work and have been brushing up on various computer science algorithms to possibly help with my job search. The two problems presented below are known as the Travelling Saleswoman problem and the Knapsack problem.

The first one basically asks the question, if you had multiple points that you had to travel to around a city, what would be the shortest path to and from each of those points (assuming you only had to visit them once). The answer to this also depends where your starting point is of course. The slow way of solving it involves calculating all of the combinatorial paths (factorial tries) and finding the shortest length.

The second problem involves attempting to fit a set of different sized boxes (filled with different amounts of money in each box) in a knapsack that can only hold a certain amount of mass. The goal is to try and maximize the amount of boxes and money that you can fit in the knapsack which again involves trying a series of combinations for each box to fit. The problem also gets harder if you allow multiple boxes of the same type to fit inside the knapsack as it expands the number of attempts needed to try and find the best fit.

Anyway, here’s some code below (no comments or guarantee of code correctness) which helped me study these concepts in practice:

the_travelling_saleswoman_with_a_knapsack_problem.py

#!/usr/bin/python

import math
import os
import sys

def d(a, b):
	return math.sqrt(math.pow(b[0] - a[0], 2) + math.pow(b[1] - a[1], 2))

def brute_force(left, ban=[]):
	flag = False
	flist = []
	for i in left:
		if (i in ban):
			continue
		flag = True
		ban.append(i)
		ulist = brute_force(left, ban)
		for uitem in ulist:
			flist.append(uitem)
		ban.remove(i)
	if (len(flist) > 0):
		return flist
	if (flag == False):
		return [ban[:]]
	return []

def travelling_saleswman(items):
	leng = len(items)
	indx = range(0, leng)
	uniq = brute_force(indx)
	minl = []; mind = 0
	for i in uniq:
		path = []; dist = 0
		x = 0
		while ((x + 1) < leng):
			path.append(items[i[x]])
			dist += d(items[i[x]], items[i[x+1]])
			x += 1
		path.append(items[i[x]])
		dist = math.ceil(dist)
		#print("Path",path,dist)
		if ((mind < 1) or (dist < mind)):
			minl = path[:]; mind = dist
	print("BF-Min",minl,mind)

def nearest_item(items):
	leng = len(items)
	minl = []; minm = 0
	for i in range(0, leng):
		temp = items[:]
		start = [temp.pop(i)]; minp = 0
		while (len(temp) > 0):
			mini = 0; mind = 0
			j = (len(start) - 1)
			x = 0; l = len(temp)
			while (x < l):
				dist = d(start[j], temp[x])
				if ((mind < 1) or (dist < mind)):
					mini = x; mind = dist
				x += 1
			start.append(temp.pop(mini))
			minp += mind
		minp = math.ceil(minp)
		if ((minm < 1) or (minp < minm)):
			minl = start[:]; minm = minp
		#print("Path",start,minp)
	print("NN-Min",minl,minm)

def knapsack_one(pkgs):
	leng = len(pkgs)
	indx = range(0, leng)
	uniq = brute_force(indx)
	maxl = []; maxs = 0; maxm = 0
	for item in uniq:
		size = 0; money = 0
		temp = []
		for i in item:
			if ((pkgs[i][0] + size) > 15):
				break
			temp.append(pkgs[i]); size += pkgs[i][0]; money += pkgs[i][1]
		#print("Pkgs",temp,"%dk / $%d"%(size,money))
		if ((maxm < 1) or (money > maxm) or ((money == maxm) and (size > maxs))):
			maxl = temp[:]; maxs = size; maxm = money
	print("KS-One",maxl,"%dk / $%d"%(maxs,maxm))

def knapsack_many(pkgs):
	leng = len(pkgs)
	indx = range(0, leng)
	uniq = brute_force(indx)
	maxl = []; maxs = 0; maxm = 0
	for item in uniq:
		size = 0; money = 0
		temp = []
		for i in item:
			if ((pkgs[i][0] + size) > 15):
				break
			temp.append(pkgs[i]); size += pkgs[i][0]; money += pkgs[i][1]
		#print("PKGS-One",temp,"%dk / $%d"%(size,money))
		tlist = temp[:]; tsize = size; tmoney = money
		# attempt to add in as many larger packages as possible (highest mass first)
		z = (leng - 1); x = 0
		while (z >= (leng / 2)):
			temp = tlist[:]; size = tsize; money = tmoney
			y = z
			while (y > -1):
				if ((pkgs[y][0] + size) > 15):
					y -= 1
					continue
				temp.append(pkgs[y]); size += pkgs[y][0]; money += pkgs[y][1]
			z -= 1
			# attempt to squeeze in as many smaller packages as possible (lowest mass first)
			slist = temp[:]; ssize = size; smoney = money
			y = 0
			while (y <= (leng / 2)):
				temp = slist[:]; size = ssize; money = smoney
				i = (len(temp) - 1)
				while (i >= (len(temp) / 2)):
					#print("PKGS-Many",temp,"%dk / $%d"%(size,money))
					if ((maxm < 1) or (money > maxm) or ((money == maxm) and (size > maxs))):
						maxl = temp[:]; maxs = size; maxm = money
					size -= temp[i][0]; money -= temp[i][1]
					temp[i] = pkgs[y]; size += pkgs[y][0]; money += pkgs[y][1]
					while ((pkgs[y][0] + size) <= 15):
						temp.append(pkgs[y]); size += pkgs[y][0]; money += pkgs[y][1]
					i -= 1
				y += 1
	print("KS-Many",maxl,"%dk / $%d"%(maxs,maxm))

def main():
	cities = [[0, 60], [15, 30], [20, 65], [35, 25], [45, 15], [60, 55], [95, 80]]
	travelling_saleswman(cities)
	nearest_item(cities)
	# [1kg, $1], etc... (methods assume the list items are sorted by mass!)
	pkglist = [[1, 1], [1, 2], [2, 2], [4, 10], [12, 4]]
	knapsack_one(pkglist)
	knapsack_many(pkglist)

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

('BF-Min', [[45, 15], [35, 25], [15, 30], [0, 60], [20, 65], [60, 55], [95, 80]], 174.0)
('NN-Min', [[45, 15], [35, 25], [15, 30], [0, 60], [20, 65], [60, 55], [95, 80]], 174.0)
('KS-One', [[1, 1], [1, 2], [2, 2], [4, 10]], '8k / $15')
('KS-Many', [[1, 2], [4, 10], [4, 10], [4, 10], [1, 2], [1, 2]], '15k / $36')

OSI Layers – Summary
Layer 2 – Data Link – Frame (802.3/Ethernet)
Dst MAC (6 bytes)	Src MAC (6 bytes)	802.1q (4 bytes) [opt]	Type/Leng (2 bytes)
Layer 3 – Network – Packet (IPv4) Version/IHL (1 byte) DSCP/ECN (1 byte) Leng (2 bytes) Identification (2 bytes) Flags/Frag Offset (2 bytes) TTL (1 byte) Protocol (1 byte) Header Checksum (2 bytes) Src IP (4 bytes) Dst IP (4 bytes) Layer 4 – Transport – Segment (UDP) Src Port (2 bytes) Dst Port (2 bytes) Leng (2 bytes) Checksum (2 bytes)   Layer 4 – Transport – Segment (TCP) Src Port (2 bytes) Dst Port (2 bytes) Leng (2 bytes) Checksum (2 bytes) Sequence Number (4 bytes) Acknowledgment Number (4 bytes) Data Offset (1 byte) Flags (1 byte) SYN/ACK/RST/FIN Window Size (2 bytes) Layer 5/6/7 – Application – Data (DHCP/DNS/SSH/HTTP) Payload

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 [email protected]:$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