| |
| """Provisional node-level recoding of observed Linux Huff_addRef/increment semantics.""" |
| class Node: |
| __slots__=('index','left','right','parent','next','previous','head','weight','symbol') |
| def __init__(self,index,symbol=0,weight=0): |
| self.index=index;self.symbol=symbol;self.weight=weight |
| self.left=self.right=self.parent=self.next=self.previous=self.head=None |
|
|
|
|
| class Huffman: |
| def __init__(self,second=False): |
| self.nodes=[Node(0,256)];self.root=self.nyt=self.nodes[0];self.lookup={256:self.nyt};self.cells=[];self.free=None;self.second=second;self.events={} |
| def event(self,name):self.events[name]=self.events.get(name,0)+1 |
| def allocate_cell(self,node): |
| if self.free is None:i=len(self.cells);self.cells.append(node);self.event('cell_allocate') |
| else:i=self.free;self.free=self.cells[i];self.cells[i]=node;self.event('cell_reuse') |
| return i |
| def free_cell(self,i):self.cells[i]=self.free;self.free=i;self.event('cell_free') |
| def swap_tree(self,a,b): |
| pa,pb=a.parent,b.parent |
| if pa: |
| if pa.left is a:pa.left=b |
| else:pa.right=b |
| else:self.root=b |
| if pb: |
| if pb.left is b:pb.left=a |
| else:pb.right=a |
| else:self.root=a |
| a.parent,b.parent=pb,pa;self.event('tree_swap') |
| def swap_list(self,a,b): |
| a.next,b.next=b.next,a.next;a.previous,b.previous=b.previous,a.previous |
| if a.next is a:a.next=b |
| if b.next is b:b.next=a |
| for n in [a,b]: |
| if n.next:n.next.previous=n |
| if n.previous:n.previous.next=n |
| self.event('list_swap') |
| def increment(self,node): |
| if node is None:self.event('null_increment');return |
| if node.next and node.next.weight==node.weight: |
| self.event('equal_next');leader=self.cells[node.head] |
| if leader is not node.parent:self.swap_tree(leader,node) |
| else:self.event('leader_is_parent') |
| self.swap_list(leader,node) |
| if node.previous and node.previous.weight==node.weight:self.cells[node.head]=node.previous;self.event('old_head_previous') |
| else:self.free_cell(node.head) |
| node.weight=(node.weight+1)&0xffffffff |
| if node.next and node.next.weight==node.weight:node.head=node.next.head;self.event('new_head_shared') |
| else:node.head=self.allocate_cell(node) |
| if node.parent: |
| self.increment(node.parent) |
| if node.previous is node.parent: |
| self.event('post_parent_adjacent');parent=node.parent;self.swap_list(node,parent) |
| if self.cells[node.head] is node:self.cells[node.head]=parent;self.event('post_parent_head') |
| def add(self,symbol): |
| symbol&=255 |
| if symbol in self.lookup:self.event('existing');self.increment(self.lookup[symbol]);return |
| self.event('new');leaf=Node(len(self.nodes),symbol,1);internal=Node(len(self.nodes)+1,257,1);self.nodes.extend([leaf,internal]);nyt=self.nyt |
| internal.next=nyt.next |
| if internal.next: |
| internal.next.previous=internal |
| if internal.next.weight==1:internal.head=internal.next.head |
| else:internal.head=self.allocate_cell(internal) |
| else:internal.head=self.allocate_cell(internal) |
| nyt.next=internal;internal.previous=nyt |
| leaf.next=nyt.next;leaf.next.previous=leaf;leaf.head=leaf.next.head;nyt.next=leaf;leaf.previous=nyt |
| parent=nyt.parent |
| if parent: |
| if parent.left is nyt:parent.left=internal |
| else:parent.right=internal |
| else:self.root=internal |
| internal.left=nyt;internal.right=leaf;internal.parent=parent;leaf.parent=nyt.parent=internal;self.lookup[symbol]=leaf;self.increment(parent) |
| def codewords(self): |
| out={} |
| def walk(n,bits): |
| if n.symbol!=257:out[n.symbol]=bits;return |
| walk(n.left,bits+[0]);walk(n.right,bits+[1]) |
| walk(self.root,[]);return out |
| def state(self,base=0x10000): |
| def addr(n):return 0 if n is None else base+0x830+56*n.index |
| def cell(i):return 0 if i is None else base+0xb030+8*i |
| nodes=[{'index':n.index,'address':addr(n),'left':addr(n.left),'right':addr(n.right),'parent':addr(n.parent),'next':addr(n.next),'previous':addr(n.previous),'head_cell':cell(n.head),'weight':n.weight,'symbol':n.symbol} for n in self.nodes] |
| heads=sorted({n.head for n in self.nodes if n.head is not None}) |
| values=[addr(v) if isinstance(v,Node) else cell(v) for v in self.cells] |
| return {'node_count':len(nodes),'pointer_cell_count':len(self.cells),'root':addr(self.root),'list_start':addr(self.nyt),'tail_slot':addr(self.nyt) if self.second else 0,'free_head':cell(self.free),'nodes':nodes,'heads':[[cell(i),addr(self.cells[i])] for i in heads],'pointer_cells':values,'lookup':[[s,addr(n)] for s,n in sorted(self.lookup.items())]} |
|
|
