Trixy Programming

Java Native Memory Leak DeflaterOutputStream Derby or MySQL

noreply@blogger.com (Justin Beck) — Thu, 24 Dec 2009 08:12:00 +0000

So with some more recent database code. We we're compressing data elements before writing them to the database. Well our servers kept running out of memory. I mean Gigs and Gigs of memory.

Traced it down to if you don't call Session.End() on GZIPOutputStream or DeflaterOutputStream it will leak large amounts of Native memory.

This article has more details.

Native memory leaks suck to debug, took us about a week to find this. I hope this helps some other people.

Ultramon for Windows 7

noreply@blogger.com (Justin Beck) — Thu, 24 Dec 2009 08:06:00 +0000

Ultramon Beta is great for Windows 7

Works like a charm with even nice start menu;s

Download it here

Solution to Skype 3.8 on Windows 7

noreply@blogger.com (Justin Beck) — Thu, 24 Dec 2009 08:05:00 +0000

So I hate Skype 4.0 they just messed too much stuff up for me. So I like to run the old version of skype 3.8 but it doesn't work for Windows 7.

The solution, run Skype 3.6

I can confirm this build works (oldapps.com)

Alcohol 52% Windows 7 mount mds or iso Disk Images

noreply@blogger.com (Justin Beck) — Thu, 24 Dec 2009 08:03:00 +0000

Recently I upgraded to Windows 7. Alcohol 52% no longer works. :-(

Lucky Daemon Tools Lite works on Windows 7 and is a nice replacement. Sometimes I still use Alcohol 52% on Windows Vista to make images

Download this version

C# POP3 Library with SSL for Gmail

noreply@blogger.com (Justin Beck) — Sat, 11 Jul 2009 21:20:00 +0000

So I ended up searching for hours trying to find a free C# library to do POP3 access to a SSL server like gmail. In our company we use Google Apps and we like gmail's mail server, it would be nice to be able to have programmatical access to these mail accounts. How does this not exist?

So this solution takes OpenPop.net Open source library and makes some very small tweaks so it has Ssl support.

Here is the important simple code snippet.

Stream actualstream = clientSocket.GetStream();

if (useSSL) {
System.Net.Security.SslStream sslstream = new SslStream(clientSocket.GetStream());
sslstream.AuthenticateAsClient(strHost);
actualstream = sslstream;
}

Attached here is the re zip of the source code with the change to the library and also a tweak to the sample app with a checkbox to include SSL support.

OpenPOP with SSL Source Download

OpenPOP with SSL Binaries Download

Enjoy!

Generating Control Logic for 5 stage pipeline Processor Verilog

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:58:00 +0000

This one takes a little while to explain but is a really bright idea. Control logic for a processor is one of the most confusing parts. Especially if this is your first processor your building. Cranking out a Control Logic Table in excel or something is very valuable because it allows you to see how it all works out.

I wrote a little ruby script to generate verilog control code based on my spread sheet. Not only do you not have to code any control logic, but fixing control logic bugs are really easy because it is all in the spread sheet.

Ruby Script:


require 'pp'

def clean(str)
  if str.rindex("b")
    return str[1...str.size]
   else
     return str
  end
    
  
end
@size = []
@wirename = []
@table = []

File.open('table.txt','r') do |f|
    @size = f.gets.split("\t").map{|x| x.strip }
    @wirename = f.gets.split("\t").map{|x| x.strip }
  f.readlines.each do |l|
    @table << l.split("\t").map{|x| x.strip } 
  end  
end

@size.delete_at(0)
@size.delete_at(0)

@wirename.delete_at(0)
@wirename.delete_at(0)

@wiredefs = []
@assignments = []

#pp @size
#pp @wirename
#pp @table

#wire assignments
cur = 0
@wirename.each_with_index do |n,i|
  puts n
  df = ""
  sz = @size[i].to_i
  if sz == 1
    df ="wire "
    ass = "assign " + n.to_s + " = data[" + cur.to_s + "];"
  else
    df = "wire[" + (sz-1).to_s + ":0] "   
    ass = "assign " + n.to_s + " = data[" + (cur+sz-1).to_s + ":" + cur.to_s + "];"
  end
    df +=n.to_s + ";"  
  
  
  cur += sz
  @wiredefs << df
  @assignments <<  ass
  end
datasize = 0
File.open ('export.v','w') do |v|

v.puts @wiredefs.join("\n")



@table.each {|x|
  data = x[2...x.size] 
  data = data.reverse
  data = data.map {|c| clean(c)}
  q = data.join
  code = "data = 32'b"  + q
  datasize =  q.size if q.size > datasize


  v.puts "7'b" + x[0] + ": " + code + " ;" + '//' + x[1].to_s
}

v.puts @assignments.join("\n")
end
puts "data size: " + datasize.to_s

Example Verilog output:


wire pc_en;
wire muxI;
wire[1:0] muxJ;
wire pc_select;
wire reg_write;
wire[1:0] rd_select;
wire sign_ext;
wire[1:0] sign_ext_mask;
wire[1:0] alu_rt_select;
wire alu_rs_select;
wire[1:0] alu_op;
wire[1:0] alu_cin_sign;
wire[1:0] alu_anot_bnot;
wire[1:0] shifter_op;
wire[2:0] logic_op;
wire exe_select;
wire save_select;
wire mem_write;
wire[2:0] write_select;
wire pc_add_select;
5'b00000: data = 32'bxxxx0xxxxxxxxxxxxxxxxxxxxx0xxxx0 ;//HALT
5'b00001: data = 32'bx0000x1xxxxx000100000xxxxx00xx01 ;//NOP
5'b01000: data = 32'bx0000x1xxxxx0001000101010010xx01 ;//ADDI
5'b01001: data = 32'bx0000x1xxxxx1011000101010010xx01 ;//SUBI
5'b01010: data = 32'bx0000x1xxxxx00xx100101000010xx01 ;//XORI
5'b01011: data = 32'bx0000x1xxxxx01xx110101000010xx01 ;//ANDNI
5'b10100: data = 32'bx0000x0xxx00xxxxxxx10xxx0010xx01 ;//ROLI
5'b10101: data = 32'bx0000x0xxx01xxxxxxx10xxx0010xx01 ;//SLLI
5'b10110: data = 32'bx0000x0xxx10xxxxxxx10xxx0010xx01 ;//SRAI
5'b10111: data = 32'bx0000x0xxx11xxxxxxx10xxx0010xx01 ;//SRLI
5'b10000: data = 32'bxxxx111xxxxx000100010101xx00xx01 ;//ST
5'b10001: data = 32'bx0100x1xxxxx0001000101010010xx01 ;//LD
5'b10011: data = 32'bx000111xxxxx0001000101010110xx01 ;//STU
5'b11001: data = 32'bx0010xx1xxxx00xx11001xxx1010xx01 ;//TM
5'b11011: data = 32'bx0000x1xxxxx000100001xxx1010xx01 ;//ADD
5'b11011: data = 32'bx0000x1xxxxx101100001xxx1010xx01 ;//SUB
5'b11011: data = 32'bx0000x1xxxxx00xx10001xxx1010xx01 ;//XOR
5'b11011: data = 32'bx0000x1xxxxx01xx11001xxx1010xx01 ;//ANDN
5'b11010: data = 32'bx0000x0xxx00xxxxxxx01xxx1010xx01 ;//ROL
5'b11010: data = 32'bx0000x0xxx01xxxxxxx01xxx1010xx01 ;//SLL
5'b11010: data = 32'bx0000x0xxx10xxxxxxx01xxx1010xx01 ;//SRA
5'b11010: data = 32'bx0000x0xxx11xxxxxxx01xxx1010xx01 ;//SRL
5'b11100: data = 32'bx0010xx000xx101000001xxx1010xx01 ;//SEQ
5'b11101: data = 32'bx0010xx001xx101000001xxx1010xx01 ;//SLT
5'b11110: data = 32'bx0010xx010xx101000001xxx1010xx01 ;//SLE
5'b11111: data = 32'bx0010xx011xx000000001xxx1010xx01 ;//SCO
5'b01100: data = 32'b0xxx0xxxxxxx00xx01000011xx0x0111 ;//BEQZ
5'b01101: data = 32'b0xxx0xxxxxxx00xx01000011xx0x0011 ;//BNEZ
5'b01110: data = 32'b0xxx0xxxxxxxxxxxxxxxx011xx0x1111 ;//BLTZ
5'b01111: data = 32'b0xxx0xxxxxxxxxxxxxxxx011xx0x1011 ;//BGEZ
5'b11000: data = 32'bx0110xxxxxxxxxxxxxx100110110xx01 ;//LBI
5'b10010: data = 32'bx0000x1xxxxx00xx011100100110xx01 ;//SLBI
5'b00100: data = 32'b0xxx0xxxxxxxxxxxxxxxx001xx01xx01 ;//J
5'b00101: data = 32'b1xxx0xxxxxxxxxxxxxxxx011xx01xx01 ;//JR
5'b00110: data = 32'b01000xxxxxxxxxxxxxxxx0011111xx01 ;//JAL
5'b00111: data = 32'b11000xxxxxxxxxxxxxxxx0111111xx01 ;//JALR
assign pc_en = data[0];
assign muxI = data[1];
assign muxJ = data[3:2];
assign pc_select = data[4];
assign reg_write = data[5];
assign rd_select = data[7:6];
assign sign_ext = data[8];
assign sign_ext_mask = data[10:9];
assign alu_rt_select = data[12:11];
assign alu_rs_select = data[13];
assign alu_op = data[15:14];
assign alu_cin_sign = data[17:16];
assign alu_anot_bnot = data[19:18];
assign shifter_op = data[21:20];
assign logic_op = data[24:22];
assign exe_select = data[25];
assign save_select = data[26];
assign mem_write = data[27];
assign write_select = data[30:28];
assign pc_add_select = data[31];

Example Excel File(csv):


  1 1 2 1 1 2 1 2 2 1 2 2 2 2 3 1 1 1 3 1
  pc_en muxI muxJ pc_select reg_write rd_select sign_ext sign_ext_mask alu_rt_select alu_rs_select alu_op alu_cin_sign alu_anot_bnot shifter_op logic_op exe_select save_select mem_write write_select pc_add_select
00000xx HALT 0 x bxx x 0 xx x xx xx x xx xx xx xx xxx x x 0 xxx x
00001xx NOP 1 0 bxx 0 0 bxx x xx b00 0 b00 b01 b00 bxx bxxx 1 x 0 b000 x
01000xx ADDI 1 0 bxx 0 1 b00 1 b10 b10 0 b00 b01 b00 bxx bxxx 1 x 0 b000 x
01001xx SUBI 1 0 bxx 0 1 b00 1 b10 b10 0 b00 b11 b10 bxx bxxx 1 x 0 b000 x
01010xx XORI 1 0 bxx 0 1 b00 0 b10 b10 0 b10 bxx b00 bxx bxxx 1 x 0 b000 x
01011xx ANDNI 1 0 bxx 0 1 b00 0 b10 b10 0 b11 bxx b01 bxx bxxx 1 x 0 b000 x
10100xx ROLI 1 0 bxx 0 1 b00 0 10 b10 x bxx bxx bxx b00 bxxx 0 x 0 b000 x
10101xx SLLI 1 0 bxx 0 1 b00 0 10 b10 x bxx bxx bxx b01 bxxx 0 x 0 b000 x
10110xx SRAI 1 0 bxx 0 1 b00 0 10 b10 x bxx bxx bxx b10 bxxx 0 x 0 b000 x
10111xx SRLI 1 0 bxx 0 1 b00 0 10 b10 x bxx bxx bxx b11 bxxx 0 x 0 b000 x
10000xx ST 1 0 bxx 0 0 bxx 1 b10 b10 0 b00 b01 b00 bxx bxxx 1 1 1 bxxx x
10001xx LD 1 0 bxx 0 1 b00 1 b10 b10 0 b00 b01 b00 bxx bxxx 1 x 0 b010 x
10011xx STU 1 0 bxx 0 1 b01 1 b10 b10 0 b00 b01 b00 bxx bxxx 1 1 1 b000 x
11001xx TM 1 0 bxx 0 1 b10 x bxx b01 0 b11 bxx b00 bxx b1xx x x 0 b001 x
1101100 ADD 1 0 bxx 0 1 b10 x bxx b01 0 b00 b01 b00 bxx bxxx 1 x 0 b000 x
1101101 SUB 1 0 bxx 0 1 b10 x bxx b01 0 b00 b11 b10 bxx bxxx 1 x 0 b000 x
1101110 XOR 1 0 bxx 0 1 b10 x bxx b01 0 b10 bxx b00 bxx bxxx 1 x 0 b000 x
1101111 ANDN 1 0 bxx 0 1 b10 x bxx b01 0 b11 bxx b01 bxx bxxx 1 x 0 b000 x
1101000 ROL 1 0 bxx 0 1 b10 x bxx b01 x bxx bxx bxx b00 bxxx 0 x 0 b000 x
1101001 SLL 1 0 bxx 0 1 b10 x bxx b01 x bxx bxx bxx b01 bxxx 0 x 0 b000 x
1101010 SRA 1 0 bxx 0 1 b10 x bxx b01 x bxx bxx bxx b10 bxxx 0 x 0 b000 x
1101011 SRL 1 0 bxx 0 1 b10 x bxx b01 x bxx bxx bxx b11 bxxx 0 x 0 b000 x
11100xx SEQ 1 0 bxx 0 1 b10 x bxx b01 0 b00 b10 b10 bxx b000 x x 0 b001 x
11101xx SLT 1 0 bxx 0 1 b10 x bxx b01 0 b00 b10 b10 bxx b001 x x 0 b001 x
11110xx SLE 1 0 bxx 0 1 b10 x bxx b01 0 b00 b10 b10 bxx b010 x x 0 b001 x
11111xx SCO 1 0 bxx 0 1 b10 x bxx b01 0 b00 b00 b00 bxx b011 x x 0 b001 x
01100xx BEQZ 1 1 b01 x 0 bxx 1 b01 b00 0 b01 bxx b00 bxx bxxx x x 0 bxxx 0
01101xx BNEZ 1 1 b00 x 0 bxx 1 b01 b00 0 b01 bxx b00 bxx bxxx x x 0 bxxx 0
01110xx BLTZ 1 1 b11 x 0 bxx 1 b01 bxx x bxx bxx bxx bxx bxxx x x 0 bxxx 0
01111xx BGEZ 1 1 b10 x 0 bxx 1 b01 bxx x bxx bxx bxx bxx bxxx x x 0 bxxx 0
11000xx LBI 1 0 bxx 0 1 b01 1 b01 b10 x bxx bxx bxx bxx bxxx x x 0 b011 x
10010xx SLBI 1 0 bxx 0 1 b01 0 b01 b10 1 b01 bxx b00 bxx bxxx 1 x 0 b000 x
00100xx J 1 0 bxx 1 0 bxx 1 b00 bxx x bxx bxx bxx bxx bxxx x x 0 bxxx 0
00101xx JR 1 0 bxx 1 0 bxx 1 b01 bxx x bxx bxx bxx bxx bxxx x x 0 bxxx 1
00110xx JAL 1 0 bxx 1 1 b11 1 b00 bxx x bxx bxx bxx bxx bxxx x x 0 b100 0
00111xx JALR 1 0 bxx 1 1 b11 1 b01 bxx x bxx bxx bxx bxx bxxx x x 0 b100 1

Lazy List in Ruby

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:39:00 +0000

A Lazy List is a list that evaluates and constructs it self as it is used. Very much a functional language concept.


class LazyList
  attr_accessor :head, :tail


  def initialize(h, t)  
    @head = h
    @tail = t
  end

  def nil?
    return head.nil?
  end
  
  def self.null
    return LazyList.new(nil, nil)
  end
  
  def self.seq(start, finish)
    if start > finish
      return LazyList.null
    else
      return LazyList.new(start, proc { seq( start + 1, finish) })
    end  
  end
  
  def self.infseq(start)
    return LazyList.new(start, proc { infseq( start + 1 ) })  
  end
  
  
  def self.constList(val)
    return LazyList.new(val, proc { constList(val) })
  end
  
  def self.boolseq(start)
    return LazyList.new(start, proc { boolseq(!start) })
  end
  
  
  def self.filter(listcontrol, listdata)
    if listcontrol.nil? || listdata.nil?
      return LazyList.new
    end
    
    if listcontrol.head
      LazyList.new(listdata.head, proc { filter(listcontrol.tail.call, listdata.tail.call)})
    else
      filter(listcontrol.tail.call, listdata.tail.call)
    end
    
  end
  
  def Nth(n)
    return if nil?
    
    if n == 0
      return head
    else
      tail.call.Nth(n-1)
    end
  end
  
  def self.filter_check(data, check)
    if nil?
      return
    end
    
    if data.head % check != 0
      LazyList.new(data.head, proc { filter_check(data.tail.call, check)})
    else
      filter_check(data.tail.call, check)
    end
    
  end
  
  def self.prime_help(list)
    return LazyList.new(list.head, proc { prime_help(filter_check(list.tail.call, list.head))})
  end
  
  def self.primes
    return prime_help(infseq(2))
  end
  
  def printN(n)
    if nil?
      return
    end
    
    puts head
    if n >= 0 && !tail.nil?
      tail.call.printN(n-1)
    end
  end
end

l = LazyList.seq(2, 8)
l.printN(34)
l = LazyList.infseq(3)
l.printN(34)
b = LazyList.boolseq(false)
b.printN(6)
f = LazyList.filter(b,l)
f.printN(6)

a = LazyList.primes()
a.printN(8)
puts "nth #{f.Nth(2)}"

Make Sublists in Scheme

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:37:00 +0000

A fairly useful function in scheme is to turn a list of elements into a list of list of elements

example: [1,2,3] => [[1], [2], [3]]

(define (make-sublists l)
  (map (lambda (x) (list x )) l))

Tree Map Scheme

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:33:00 +0000

Very similar to the Map function for a list in scheme, you can apply a map to a tree.
This traverses the entire tree applying a map function to the value and stuffing back into a tree.

(define (tree-map f t)
  (if (null? t)
      ()
      (if (null? (cdr t))
          ()
          (append (append (tree-map f (car t)) 
                  (list (f (cadr t)))) 
                  (tree-map f (caddr t))))
      ))

Valid and Equal Binary Tree Scheme

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:33:00 +0000

This is one possible way of determining whether two binary trees are equal. Granted this implementation is dependent on them being valid. Which is that they are both symmetric around the top head node.

(define (valid-bintree? t)
  (if (null? t)
      #t
      (if (list? t)
          (if (valid-bintree? (car t))
              (if (valid-bintree? (caddr t))
                  #t
                  #f)
              #f)
          #f)
      ))

(define (equal-bintrees? a b)
  (if (null? a) 
      (if (null? b)
          #t
          #f)
      (if (null? b)
          #f
          (if (and (valid-bintree? a) (valid-bintree? b))
              (and (= (cadr a) (cadr b)) (equal-bintrees?(car a) (car b)) (equal-bintrees?(caddr a) (caddr b)))
              #f)
          )
      ))

Extend Function Scheme

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:23:00 +0000

See merge and distrib for reference.
An extend function is a pretty handy function for doing some advance list procedures.


(define (extend L E)
  (merge L (distrib L E))
  )

Subsets function in Scheme

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:23:00 +0000

Subsets computes all the possible subsets possible for a list of unique values.


(define (subsets L)
  (if (null? L)
      (list ())
      (extend (subsets (cdr L)) (car L))
      ))

Distrib function Scheme

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:22:00 +0000


(define (distrib L E)
  (if (null? L)
      ()
      (cons (cons E (car L))
    (distrib (cdr L) E))
      ))

Merge List in Scheme

noreply@blogger.com (Justin Beck) — Mon, 22 Dec 2008 06:21:00 +0000


(define (merge a b)
  (if (null? a)
      b
      (if (null? b)
          a
          (if (< (length (car a)) (length (car b)))
              (append (list (car a)) (merge (cdr a) b))
              (append (list (car b)) (merge (cdr b) a))
              ))))

Binary Search Tree in Java

noreply@blogger.com (Justin Beck) — Sun, 21 Dec 2008 23:01:00 +0000


import java.io.PrintWriter;

public class BinaryTreeNode {
 
 private Comparable key;
 private Object data;
 private BinaryTreeNode left;
 private BinaryTreeNode right;
 
 public BinaryTreeNode(Comparable pKey, Object pData)
 {
  key = pKey;
  data = pData;
 }

 /**
  * @return Returns the data.
  */
 public Object getData() {
  return data;
 }

 /**
  * @param data The data to set.
  */
 public void setData(Object data) {
  this.data = data;
 }

 /**
  * @return Returns the key.
  */
 public Comparable getKey() {
  return key;
 }

 /**
  * @param key The key to set.
  */
 public void setKey(Comparable key) {
  this.key = key;
 }

 /**
  * @return Returns the left.
  */
 public BinaryTreeNode getLeft() {
  return left;
 }

 /**
  * @param left The left to set.
  */
 public void setLeft(BinaryTreeNode left) {
  this.left = left;
 }

 /**
  * @return Returns the right.
  */
 public BinaryTreeNode getRight() {
  return right;
 }

 /**
  * @param right The right to set.
  */
 public void setRight(BinaryTreeNode right) {
  this.right = right;
 }
 
 

}

public class BinarySearchTree implements Dictionary {

 private BinaryTreeNode mRoot;
 private int mNumberItems=0;
 
 /* insert
  * -exact same functionality as update, see update (drops the return value though)
  */
 public void insert(Comparable key, Object data) {
  update(key,data);
   

 }
 /*recrusiveUpdateChild
  * -runs through the entire tree, and updates a child with new data,
  * -if the child doesn't exist, it is add at the appropriate branch ending
  * 
  * returns true if update a node
  * returns false if added a child at the end of the branch
  * 
  */
 private boolean recurisiveUpdateChild(BinaryTreeNode parent, Comparable key, Object data)
 {
  if (key.compareTo(parent.getKey())==0)
  {   
   parent.setData(data);
   return true; //replaced an associated data node
  }
  if (key.compareTo(parent.getKey())<0)
  {
   if (parent.getLeft()==null)
   {
    
    parent.setLeft(new BinaryTreeNode(key,data));
    mNumberItems++;
    return false; //no replacement, addition to the tree
   }
   return recurisiveUpdateChild(parent.getLeft(),key,data);   
  }
  else
  {
   if (parent.getRight()==null)
   {
    parent.setRight(new BinaryTreeNode(key,data));
    mNumberItems++;
    return false; // no replacement
   }
   return recurisiveUpdateChild(parent.getRight(),key,data);
  }
  
  
 }
/*Update
 *  -Provides add, and modify functionality
 *  
 *  -returns true if it did a modify
 *  -returns false if it did an add
 */
 public boolean update(Comparable key, Object data) {
  if (mRoot==null)
  {
   mRoot = new BinaryTreeNode(key,data);
   mNumberItems++;
   return false;
  }
  else
  {
   return recurisiveUpdateChild(mRoot,key,data);
  }
 }
/*recursiveLookupChild
 * -simple lookup, traverses through the tree
 * 
 * returns the associated data of the found node, if it found one
 * 
 * returns null - if no node was found (fell off the tree) 
 * 
 */
 private Object recurisiveLookupChild(BinaryTreeNode parent, Comparable key)
 {
  if (key.compareTo(parent.getKey())==0)
  {      
   return parent.getData();
  }
  if (key.compareTo(parent.getKey())<0)
  {
   if (parent.getLeft()==null) //fell off the tree
   {
    return null;    
   }
   else
   {
   return recurisiveLookupChild(parent.getLeft(),key);
   }
  }
  else
  {
   if (parent.getRight()==null) //fell off the tree
   {
    return null;    
   }
   else
   {
    return recurisiveLookupChild(parent.getRight(),key);
   }   
  }  
 }
 
 /*lookup
  * -looksup the data from the tree
  * returns Data or null if not found
  */
 public Object lookup(Comparable key) {
  if (mRoot==null) return null;
  
  return recurisiveLookupChild(mRoot,key);
 }
/*size
 *  returns number of items in tree
 */
 public int size() {
  return mNumberItems;
 }
/*print
 *  does an inorder traversal, printing out a sorted list of items
 */
 public void print(PrintWriter p) {
  //p.println("Printing Binary Search Tree");
  printNode(mRoot,p);
 }
 /*printnode
  * -recursive aux method for the print funcationality
  */
 private void printNode(BinaryTreeNode node,PrintWriter p)
 {
  if (node==null) return;
  //simple inorder traversal
  printNode(node.getLeft(),p);
  
  p.print(node.getKey());
  p.print(" ");
  p.println(node.getData());
  
  printNode(node.getRight(),p);  
 }
}

Sorted Arraylist in Java

noreply@blogger.com (Justin Beck) — Sun, 21 Dec 2008 23:00:00 +0000


public class SortedArrayList implements Dictionary {

 //number of items in the array
 private int mNumberItems=0;
 
 private DictionaryItem mItems[] = new DictionaryItem[10];
 /*expand array
  * -checks to see if array needs expansion, if so, it builds a new array
  */
 private void expandArray()
 {
  if (checkExpandArray())
  {
    DictionaryItem newarray[] = new DictionaryItem[mItems.length*2];
    System.arraycopy(mItems,0,newarray,0,mNumberItems); // copy all items into the new array
    mItems = newarray;
  }  
 }
 /*checkExpandArray
  *-if the numberofitems in the array is getting large, increase the size of the array to make room for another item 
  */
 private boolean checkExpandArray()
 {
  if (mNumberItems+1>=mItems.length)
  {
   return true;   
  }
  return false;  
 }
 /*insert
  *  -see update, same functionality, just drops the return value
  */
 public void insert(Comparable key, Object data) {
  update(key,data);

 }
 /*InsertIntoArray
  * -Copies the data over in the array to make room
  * -then slips the new value into that index
  */
 private void insertIntoArray(int index, DictionaryItem item)
 {
   System.arraycopy(mItems,index,mItems,index+1,mNumberItems-index); // copy all items infront of the index
   mItems[index] = item;
 }
 /*getIndexForKey
  * does a linear search to find out where a certain key should be inserted
  */
 private int getIndexForKey(Comparable key)
 {
  int i;
  for(i=0;i<= mNumberItems-1;i++)
  {
   DictionaryItem curr = mItems[i];
   
   if(curr.getKey().compareTo(key) >=0)
   {
    return i;
   }
  }
  return mNumberItems;
 }
 /*getKeyAt
  * -returns the key at a certain index
  */
 private Object getKeyAt(int index)
 {  
  return mItems[index].getKey();
 }
 /*lookupIndexForKey
  * -does a binary search for a certain index location
  * -returns -1 if value not found
  */
 private int lookupIndexForKey(Comparable key)
 {
  return auxBinSearch(key,0,mNumberItems-1);
 }
 /*auxBinSearch
  * -is the aux recursive method to implement the binary search
  */
 private int auxBinSearch(Comparable key, int startindex,int endindex)
 {
  if (startindex > endindex) return -1;
  int mid = (startindex + endindex)/2;
  
  if (key.compareTo(getKeyAt(mid))==0) return mid;
  if (key.compareTo(getKeyAt(mid))<0)
   return auxBinSearch(key,startindex,mid-1); //go left
  else
   return auxBinSearch(key,mid+1,endindex);//go right
  
 }
 
 
/*update
 * -provides update functionality (insert, and replace
 * returns true if it replaced
 * returns false if inserted new record
 */
 public boolean update(Comparable key, Object data) {
  
  int insertindex=lookupIndexForKey(key);
  
  if (insertindex!=-1)
  {   
   mItems[insertindex] = new DictionaryItem(key,data);
   return true;
  }
  
   //now we have to insert  
   //perform linear search and get insert location
   insertindex= getIndexForKey(key);
   
   expandArray();
    
   insertIntoArray(insertindex,new DictionaryItem(key,data));
   mNumberItems++;  
   return false;
  
  
  
 }
/*lookup
 * -uses a binary search to retrieve an object
 *  returns the Object if found
 *  return null if not found
 */
 public Object lookup(Comparable key) {
  int index = lookupIndexForKey(key);
  
  if (index <0 || index > mNumberItems-1) return null;
  return mItems[index].getData();  
 }
/*size
 *-returns number of items in the array
 */
 public int size() {
  return mNumberItems;
 }
 
/*print
 *  spits out the sorted arraylist contents
 */
 public void print(PrintWriter p) {
  //p.println("Printing Sorted ArrayList");
  for(DictionaryItem curr: mItems )
  {
   if(curr!=null)
   {
    p.print(curr.getKey());
    p.print(" ");
    p.println(curr.getData());
   }
  }

 }

}

Queue in Java

noreply@blogger.com (Justin Beck) — Sun, 21 Dec 2008 22:58:00 +0000


import java.util.ArrayList;

/*Queue
 * implements a simple queue first in, first out
 */
public class Queue {

 public Queue()
 {
  
 }
 
 private ArrayList mItems = new ArrayList();
 
 /* empty
  * -returns true if there are 0 items in the queue
  * other wise false
  */
  public boolean empty()
  {
   return mItems.isEmpty();  
  }
  /* size
   * -returns the number of items in the queue
   */
  public int size()
  {
   return mItems.size();  
  }
  /*enqueue
   * -adds a node to the back end of the queue
   * 
   */
  public void enqueue(Object obj)
  {
   mItems.add(0,obj);
  }
  /*dequeue
   * -removes the last Object from the inner list
   * other words, pulls the first Object off the front of the queue
   */
  public Object dequeue()
  {
   if (this.empty()) throw new EmptyQueueException();
   
   return mItems.remove(mItems.size()-1);  
  }
  /*peek
   * -returns the front Object of the que
   */
  public Object peek()
  {
   if (this.empty()) throw new EmptyQueueException();
   
   return mItems.get(mItems.size()-1);  
  }
 
}

Stack in Java

noreply@blogger.com (Justin Beck) — Sun, 21 Dec 2008 22:57:00 +0000


import java.util.ArrayList;
import java.util.EmptyStackException;

/* Stack class
 * A basic stack, you can push items in, last in, is first out.
 * 
 */
public class Stack {
 /// stores my data member in the stack
 private ArrayList mItems = new ArrayList();
 
 public Stack()
 {
 }
/* empty
 * -returns true if there are 0 items in the stack
 * other wise false
 */
 public boolean empty()
 {
  return mItems.isEmpty();  
 }
 /* size
  * -returns the number of items in the stack
  */
 public int size()
 {
  return mItems.size();  
 }
 /*push
  * -adds an object to the Top of the stack
  */
 public void push(Object obj)
 {
  mItems.add(obj);
 }
 /*pop
  * -removes the top object from the stack and returns it
  * throws EmptyStackException if stack is empty
  */
 public Object pop()
 {
  if (this.empty()) throw new EmptyStackException();
  
  return mItems.remove(mItems.size()-1);
  
 }
 /*peek
  * -returns the current top object in the stack
  * DOES NOT REMOVE IT
  */
 public Object peek()
 {
  if (this.empty()) throw new EmptyStackException();
  
  return mItems.get(mItems.size()-1);
 }
}

Double Linked List in Java

noreply@blogger.com (Justin Beck) — Sun, 21 Dec 2008 22:55:00 +0000


/**
 * LinkedList
 * 
 * This is the core List class
 * Provides a facility to a doublly linked list.
 * 
 * Has Header Node optimization
 * Has LastNode optimization as well
 * 
 * Future Features:
 * Optimized iterator support
 * actually use some more of the optimization doublly linked lists gives you
 * 
 */

/**
 * ListNode
 * 
 * -The workhorse of the LinkedList Class
 * 
 * Provides a doublely linked potencial to other list nodes
 * Provides recursion for relative position Node lookups
 * Provides automatic linking of next and previous nodes
 * 
 */
public class ListNode
{
 /**
  * Blank constructor
  */
 public ListNode()
 {
 }
 /**
  * Purposeful constructor:
  * passes data, and previous node, allows you to build node lists, easily by chaining
  */
 public ListNode(Object pData,ListNode pPrevious)
 {
  mData = pData;
  if (pPrevious != null) //since you can pass null to it
  {
   pPrevious.setNext(this); //automatic hook up
  }
 }

 private Object mData; // stores the Object of value here

 //Accessors to the Data Object
 public Object getData()
 {
  return mData;
 }
 public void setData(Object obj)
 {
  mData = obj;
 }

 
 private ListNode mNext; // stores link to the next node in the list
 //accessor to the Next reference
 public ListNode getNext()
 {
  return mNext;
 }
 /**
  * Automatic linking on setNext
  * -set the mNext field's data
  * but also will automaticly link the "nextNodes previous link to this Node's
  */
 public void setNext(ListNode pNode)
 {
  mNext = pNode;
  if (mNext != null)
  {
   mNext.mPrevious = this; //internal auto link MUST USE INTERNAL, If you use mNext.setPrevious infinite loop become evident
  }
 }

 private ListNode mPrevious;
 //public accessor to Previous Link
 public ListNode getPrevious()
 {
  return mPrevious;
 }
  /**
   * Automatic linking on setPrevious
   * -set the mPrevious field's data
   * but also will automaticly link the "previousNodes next link to this Node's
   */
 public void setPrevious(ListNode pNode)
 {
  mPrevious = pNode;
  if (mPrevious != null)
  {
   mPrevious.mNext = this; //internal auto link MUST USE INTERNAL, If you use mPrevious.setNext infinite loop become evident
  }
 }

 /**
 * Recurisve GetNext
 * will return the node that is relativePos offset from this node only in the forward direction 
 */
 public ListNode getNextRecurisive(int relaitivePos)
 {
  if (relaitivePos <= 0) // if pos =0 return self
  {
   return this;
  }
  else
  {
   ListNode next = this.getNext(); //move to the next node
   if (next != null)
   {
    return next.getNextRecurisive(relaitivePos - 1); //Let it count the rest of the way
   }
   else
   {
    throw new IndexOutOfBoundsException("Recursive search for rel pos could not find a node soon enough");    
   }
  }

 }

public class LinkedList
{

 private ListNode mHeaderNode = new ListNode();
 private ListNode mLastNode;
 private int mNumItems = 0;

 /**
  * Constructor, sets up the default last node
  */
 public LinkedList()
 {
  mLastNode = mHeaderNode; 
 }



 /**
 * Add is your basic add operation
 *   Adds to the end of the list, using the last node optimization
*    the setNext function automaticly links in the previous links. 
*  
 */
 public void add(Object obj)
 {
  ListNode node = new ListNode(obj,null);
  mLastNode.setNext(node);
  mLastNode = node; //update the last node optimization
  mNumItems++;
 }
 /** add overload -> Insert
  *   Inserts a Object in the list node at any position
  * 
  */
 public void add(int pos, Object obj)
 {
  if (pos == mNumItems)
  {
   //special case adding at the end of the list
   add(obj); // use the regular add
   return;
  }
  IsPositionInBoundsOf(pos); //Insure the pos is a vaild pos
  ListNode node = getNode(pos);//node I am inserting at
  ListNode newNode = new ListNode(obj, node.getPrevious());
  // hook up new node to node that was behind current node
  newNode.setNext(node);  
  // hook up old node, to the new position
  mNumItems++;
 }
 /**
  * Contains
  * Returns true if LinkedList Contains a certain object
  * Object.equals is our comparer method of choice
  * 
  * other wise false
  * 
  */
 public boolean contains(Object obj)
 {
  ListNode node = mHeaderNode.getNext(); //get the first node in the list
  
  while (node != null) // go through till the end of the list
  {
   if (node.getData() != null) // check so you don't get a null ref exception
   {
    if (node.getData().equals(obj)) // use equals so.. ref type weird data types.. cough STRINGS don't hang us up
    {
     return true;
    }
   }
   else
   {
    // if null was passed we want to return true if the obj is null
    if (obj == null) return true; 
   }
   node = node.getNext(); // increment up to the next node
  }
  return false;

 }

 /**
  * IsPositionInBoundsOf
  * Returns true if pos would return a valid node in this list, if not, it will throw and indexOutOfBoundsException
  * 
  */
 protected boolean IsPositionInBoundsOf(int pos)
 {
  if (pos > mNumItems - 1)
  {
   throw new IndexOutOfBoundsException(pos + " Is out of the bounds of the List");
  }
  return true;

 }
 /**
  * get
  * Returns The object of a node at a certain position
  * 
  */
 public Object get(int pos)
 {
  IsPositionInBoundsOf(pos); // insure pos is accurate

  ListNode node = getNode(pos); //grab the node
   
  return node.getData(); //return the data ; null is ok
  
 }

 /**
  * INTERNAL METHOD
  * getNode(pos)
  * Returns the list node at a certain position
  * 
  * does a recursive search for the specified position
  * 
  */
 protected ListNode getNode(int pos)
 {
  IsPositionInBoundsOf(pos);
  return mHeaderNode.getNextRecurisive(pos + 1); // +1 because of header node
 }
 /**
  * isEmpty
  * returns true if their are 0 items in this list
  * otherwise false
  */
 public boolean isEmpty()
 {
  return mHeaderNode.getNext() == null;

 }
 /**
  * remove(pos)
  * Returns the object at the pos you are removeing from
  * Remove the last node, will re update the lastnode reference
  * 
  * deincrements the count in list
  * 
  */
 public Object remove(int pos)
 {
  IsPositionInBoundsOf(pos);
  ListNode deletednode = getNode(pos);
  if (deletednode == this.mLastNode) //last node special case
  {
   this.mLastNode = deletednode.getPrevious(); // just patch up the last node reference
  }
  deletednode.getPrevious().setNext(deletednode.getNext()); //patch the whole you just made
  
  mNumItems--;
  return deletednode.getData(); 
 }
 /**
  * size
  * Returns the number of items in this list
  */
 public int size()
 {
  return mNumItems;
 }

 //DEBUG Methods
 //remove these methods
 /**
   * Prints out the entire list of objects in list
   */
 //public void printList()
 //{
 //    System.out.println("");
 //    for (int i = 0; i < mNumItems; i++)
 //    {
 //        System.out.println(get(i));
 //    }
 //    System.out.println("");
 //}

}

Priority Queue in Java using ArrayList

noreply@blogger.com (Justin Beck) — Sun, 21 Dec 2008 22:50:00 +0000


class PriorityQueue {

    private ArrayList maxHeap;

    public PriorityQueue () {
        maxHeap = new ArrayList();
        maxHeap.add(null);   //to fill element 0
    }

    public boolean empty () {
        return maxHeap.size() == 1;
    }

    public void insert (Comparable p) {
 if (p==null) return;
 maxHeap.add(p);
 int index = maxHeap.size()-1;
 swapWithParent(index);

    }
    
 private void swapWithParent(int index)
 {
  int parentindex = index/2;
  if (parentindex==0) return;
  if (p.compareTo(maxHeap.get(parentindex)) > 0)
  {
   //swap them
   Comparable p = maxHeap.get(index);
   maxHeap.set(index,maxHeap.get(parentindex));
   maxHeap.set(parentindex,p);
   swapWithParent(parentindex);
  }
  
  
 }

}

7bit UART TX Transmitter

noreply@blogger.com (Justin Beck) — Wed, 24 Oct 2007 21:22:00 +0000

module uart_tx (output sd, output busy, input [6:0] data, input wr, rst, clk);
  reg [3:0] state, next_state;
  reg [9:0] shifter;

  parameter S_IDLE = 4'd0, S_BIT_START = 4'd1, S_BIT_P = 4'd9, S_BIT_STOP = 4'd10;

// continuous assignments
  assign busy = (state != S_IDLE);
  assign sd = shifter[0];

// synchronous behavior(s)
always @ (posedge clk) begin   
 if(rst) begin
  state <= S_IDLE;
  shifter <= 10'b11_1111_1111;
 end
 else begin
  state <= next_state;   // update state
  if(wr)     // load new frame
   shifter <= {1'b1, ~(^(data)), data, 1'b0}; // could leave stop bit off!
  else     // shift current frame
   shifter <= {1'b1, shifter[9:1]}; // shift in idle channel
 end
end
// next state logic
always @ (state, wr) begin
 case (state)
 S_IDLE:
  if(wr) next_state = S_BIT_START;
  else next_state = S_IDLE;
 S_BIT_STOP:
  next_state = S_IDLE;
 default:
  next_state = state + 4'd1;
 endcase
end

endmodule

16bit BCD adder

noreply@blogger.com (Justin Beck) — Wed, 24 Oct 2007 21:20:00 +0000

sometimes you just want a BCD adder instead of a binary adder. here is a 16bit one that works.


//put the cla and #1 adders together to make them easier to merge
module bcdadd4(
   output co,
   output [15:0] s,   
   input [15:0] a,b,
   input cin);
   wire p_up,g_up;
   wire [3:0] p,g;
   wire [3:0] carry;

   pfa_bcd add[3:0](.p(p),.g(g),.s(s),.a(a),.b(b),.cin({carry[2:0], cin}));

   cla localcla(.p_up(p_up),.g_up(g_up),.cout(carry),.p(p),.g(g),.cin(cin));

   assign co = carry[3];
endmodule

module pfa_bcd(output reg p, g, output reg[3:0] s, input cin, input[3:0] a, b);
   always @(*) begin
      s <= (a+b+cin) % 10;
      p <= (a+b == 9);
      g <= (a+b > 9);           
   end  
endmodule

16bit register file: 2 read & 2 write ports

noreply@blogger.com (Justin Beck) — Wed, 24 Oct 2007 21:12:00 +0000

This is a beautiful piece of code :-)

module reg_file(output [15:0] read1data, read2data, input [15:0] write1data, write2data, input [2:0] read1regsel, read2regsel, write1regsel, write2regsel, input clk, rst, write1, write2);
    wire [7:0] reg_final_write, reg1_write, reg2_write;
    wire [127:0] write_final_data;
    wire [127:0] regfileout;
    mux16b_8_1 muxAB [1:0] ({read1data, read2data}, {read1regsel, read2regsel}, {regfileout, regfileout}); //select 2 registers to read
    
    decoder_3_to_8 decoder(reg1_write, write1regsel, write1);   //select which register to write to
    decoder_3_to_8 decoder2(reg2_write, write2regsel, write2);   //select which register to write to
    mux16b_2_1 writeportselector [7:0] (write_final_data, reg2_write, write1data, write2data);
    
    assign reg_final_write = reg1_write | reg2_write;
    
    reg16bit reg_16wide [7:0] (regfileout, write_final_data, clk, rst, reg_final_write);   //registers    
endmodule

//sel = 0 out = a
module mux16b_2_1(output [15:0] out, input sel, input [15:0] a, b);
  assign out = (sel) ? b : a;
endmodule

module mux16b_8_1(output [15:0] out, input [2:0] sel, input [127:0] in);
  assign out = 
  (sel == 3'b000) ? in[15:0]:
  (sel == 3'b001) ? in[31:16]:
  (sel == 3'b010) ? in[47:32]:
  (sel == 3'b011) ? in[63:48]:
  (sel == 3'b100) ? in[79:64]:
  (sel == 3'b101) ? in[95:80]:
  (sel == 3'b110) ? in[111:96]: in[127:112];
endmodule

module decoder_3_to_8(output [7:0] out, input [2:0] in, input en);
  assign out =(en == 1'b0) ? 8'd0:
  (in == 3'b000) ? 8'd1:
  (in == 3'b001) ? 8'd2:
  (in == 3'b010) ? 8'd4:
  (in == 3'b011) ? 8'd8:
  (in == 3'b100) ? 8'd16:
  (in == 3'b101) ? 8'd32:
  (in == 3'b110) ? 8'd64: 8'd128;
endmodule

module reg16bit(output [15:0] dataout, input [15:0] datain, input clk, rst, en);
  wire [15:0] regin;
  assign regin = en ? datain: dataout;
  dff dff_array [15:0](dataout, regin, clk, rst);
endmodule

16bit comparer from 2bit comparer-s

noreply@blogger.com (Justin Beck) — Wed, 24 Oct 2007 21:07:00 +0000

Here is a cool idea, you can string a 2 bit comparer's together to make a big one... purely academic :-)

module compare_2bit(output A_eq_B, A_lt_B, A_gt_B, input [1:0] A, B, input A_eq_B_in, A_lt_B_in, A_gt_B_in);

  assign A_eq_B = (A == B) & A_eq_B_in;
  assign A_gt_B = (A==B) ? A_gt_B_in : A > B; 
  assign A_lt_B = (A==B) ? A_lt_B_in : (A < B);  
  
endmodule

module compare_16bit(output X_eq_Y, X_lt_Y, X_gt_Y, input [15:0] X, Y);
    
    wire[7:0] eq, lt, gt;
    compare_2bit cp [7:0] (eq, lt, gt, X, Y, {eq[6:0],1'b1}, {lt[6:0],1'b0}, {gt[6:0],1'b0});
    
    assign X_eq_Y = eq[7];
    assign X_lt_Y = lt[7];
    assign X_gt_Y = gt[7];
    
endmodule

Webbased Server monitoring Munin

noreply@blogger.com (Justin Beck) — Wed, 24 Oct 2007 20:50:00 +0000

Munin An easy way to keep track of how your servers are doing from a web front. Really clean install, and works on multitudes of servers at once.
How to set it up: How to set up Munin