File size: 4,917 Bytes
bdf6c1f | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #!/usr/bin/env python3
"""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())]}
|