prga.tools.bitgen.util module¶

class prga.tools.bitgen.util.BitstreamSegmentTree(min_gap=0)¶

Bases: prga.util.Object

A red-black tree for managing large-sized, sparse bitstream data.

Parameters:	min_gap (`int`) – Minimum gap between segments. Two segments are merged when the distance between them is smaller than this gap

Algorithmic properties:

[BST] The tree itself is a binary search tree. Data type and ordering defined in property #6.
[RBT:color-palette] Each node is either red or black.
[RBT:black-balance] Each path from root to leaf contains the same number of black nodes.
[RBT:red-isolation] Each parent-child pair cannot be both red.
[Segment] Each node [NOT just leaf nodes!] contains a bitstream segment with an offset, e.g. 8'hA5 @ [3:11].

This data type is ordered by the range, i.e. [0:2] < [3:11]. Overlapping nodes must be merged, i.e. [0:4] and [3:11] cannot co-exist in the tree.

_BitstreamSegmentTree__insert(n, p, side)¶

Insert n as the side-child of p.

Parameters:	n (`BitstreamSegmentTree._Node`) – Node to be inserted p (`BitstreamSegmentTree._Node`) – Parent node side (`0` or `1`) – `0` for left, `1` for right

classmethod _BitstreamSegmentTree__merge(n, side)¶

Merge the side-child of n into n.

Parameters:	n (`BitstreamSegmentTree._Node`) – side (`0` or `1`) –
Returns:	`n`
Return type:	`BitstreamSegmentTree._Node`

classmethod _BitstreamSegmentTree__mergedata(n, c, side)¶

Merge the data of two nodes, n and c.

Parameters:	n (`BitstreamSegmentTree._Node`) – Node that remains after the merge c (`BitstreamSegmentTree._Node`) – Node to be merged side (`0` or `1`) – `0` for left, `1` for right

_BitstreamSegmentTree__postremoval_fix(p, side, r=None)¶

Fix red/black coloring after removing black side-child of p.

Parameters:	p (`BitstreamSegmentTree._Node`) – Parent node side (`0` or `1`) – `0` for left, `1` for right r (`BitstreamSegmentTree._Node`) – Reference node. If specified, this method returns `True` if the reference node is rotated, either as the parent or the child in a rotation
Returns:	Returns `True` if `r` is moved during the fix.
Return type:	`bool`

classmethod _BitstreamSegmentTree__predecessor(n)¶: Find the immediate predecessor of n.

_BitstreamSegmentTree__rotate(n)¶

Rotate n and its parent.

Parameters:	n (`BitstreamSegmentTree._Node`) – Child node to be rotated

Notes

Property 3-5 may be violated after the rotation.

Returns:	The old parent of `n`, i.e. `p` in the figure below
Return type:	`BitstreamSegmentTree._Node`

An example (left rotate):

g                  g
 \                 \
  p                 [n]
 / \      ==>      / \
s  [n]             p   r
   / \           / \
  l   r          s   l

classmethod _BitstreamSegmentTree__successor(n)¶: Find the immediate successor of n.

class _Node(low, high, data, parent=None, is_black=False)¶

Bases: object

L = 0¶

R = 1¶

children¶

close_nephew¶

data¶

distant_nephew¶

grandparent¶

high¶

interval¶

is_black¶

is_leaf¶

is_left¶

is_red¶

is_right¶

is_root¶

left¶

low¶

parent¶

right¶

sibling¶

side¶

uncle¶

_min_gap¶

itertree(*, r=None)¶

Iterate the tree.

Yields:	`int` – low `int`: high bitarray: Little-endian, `high - low` -bits bitarray.

min_gap¶

Minimum gap between segments. Two segments are merged when the distance between them is smaller than this gap.

Type:	`int`

root¶

set_data(low, high, data)¶

Set data to the specified interval.

Parameters:	low (`int`) – high (`int`) – data (bitarray) – Little-endian, `high - low` -bits bitarray.

class prga.tools.bitgen.util.CRC(lanes=1)¶

Bases: prga.util.Object

A CRC-8 CCITT CRC calculator.

Parameters:	lanes (`int`) – Number of lanes

_mask = bitarray('11100000')¶

consume(v)¶

Consume a CRC.lanes-bit value and update the current state.

Parameters:	v (bitarray) – A `CRC.lanes`-bit value

crc¶

lanes¶

Number of lanes in this calculator.

Type:	`int`

reset()¶: Reset the current state.