Coverage for src / hodoku / solver / chain_utils.py: 83%
78 statements
« prev ^ index » next coverage.py v7.13.5, created at 2026-04-21 08:35 +0000
1"""Chain entry bit-packing utilities.
3Mirrors Java's Chain class static methods for 32-bit packed chain entries.
5Entry format (32-bit integer):
6 bits 0- 3: candidate (digit 1-9)
7 bit 4: strong link (1) or weak link (0)
8 bits 5-11: cell index 1 (0-80)
9 bits 12-18: cell index 2 (group node 2nd cell, or lower 7 bits of ALS index)
10 bits 19-25: cell index 3 (group node 3rd cell, or upper 7 bits of ALS index)
11 bits 26-29: node type (0=NORMAL, 1=GROUP, 2=ALS)
12 bits 30-31: reserved
14Entries can be negative in chain arrays to mark net branch starting points.
15All accessor functions take the absolute value before extracting fields.
16"""
18from __future__ import annotations
20# ---------------------------------------------------------------------------
21# Node type constants
22# ---------------------------------------------------------------------------
24NORMAL_NODE: int = 0
25GROUP_NODE: int = 1
26ALS_NODE: int = 2
28# ---------------------------------------------------------------------------
29# Internal masks and offsets (matching Chain.java exactly)
30# ---------------------------------------------------------------------------
32_CAND_MASK: int = 0xF # bits 0-3
33_STRONG_MASK: int = 0x10 # bit 4
34_INDEX_MASK: int = 0x7F # 7-bit index mask
35_INDEX1_OFFSET: int = 5
36_INDEX2_OFFSET: int = 12
37_INDEX3_OFFSET: int = 19
38_NO_INDEX: int = 0x7F # all bits set = "not used"
39_MODE_MASK: int = 0x3C000000 # bits 26-29
40_MODE_OFFSET: int = 26
41_GROUP_NODE_MASK: int = 0x4000000 # 1 << 26
42_ALS_NODE_MASK: int = 0x8000000 # 2 << 26
43_ALS_INDEX_MASK: int = 0x3FFF000 # bits 12-25 (14 bits total)
44_ALS_INDEX_OFFSET: int = 12
47# ---------------------------------------------------------------------------
48# Entry construction
49# ---------------------------------------------------------------------------
51def make_entry(
52 cell_index1: int,
53 cell_index2: int,
54 cell_index3: int,
55 candidate: int,
56 is_strong: bool,
57 node_type: int,
58) -> int:
59 """Create a 32-bit packed chain entry.
61 Parameters match Chain.makeSEntry(cellIndex1, cellIndex2, cellIndex3,
62 candidate, isStrong, nodeType) in Java.
63 """
64 entry = (cell_index1 << _INDEX1_OFFSET) | candidate
65 if is_strong:
66 entry |= _STRONG_MASK
67 if node_type == GROUP_NODE:
68 entry |= _GROUP_NODE_MASK
69 elif node_type == ALS_NODE:
70 entry |= _ALS_NODE_MASK
72 if cell_index2 == -1:
73 cell_index2 = 0 if node_type == NORMAL_NODE else _NO_INDEX
74 if cell_index3 == -1:
75 cell_index3 = 0 if node_type == NORMAL_NODE else _NO_INDEX
77 entry |= (cell_index2 << _INDEX2_OFFSET)
78 entry |= (cell_index3 << _INDEX3_OFFSET)
79 return entry
82def make_entry_simple(cell_index: int, candidate: int, is_strong: bool) -> int:
83 """Shorthand: normal node, no second/third cell."""
84 return make_entry(cell_index, -1, -1, candidate, is_strong, NORMAL_NODE)
87# ---------------------------------------------------------------------------
88# Entry accessors — all handle negative entries (net branch markers)
89# ---------------------------------------------------------------------------
91def get_cell_index(entry: int) -> int:
92 """First cell index (bits 5-11)."""
93 if entry < 0:
94 entry = -entry
95 return (entry >> _INDEX1_OFFSET) & _INDEX_MASK
98def get_cell_index2(entry: int) -> int:
99 """Second cell index; returns -1 if not present."""
100 if entry < 0:
101 entry = -entry
102 result = (entry >> _INDEX2_OFFSET) & _INDEX_MASK
103 return -1 if result == _INDEX_MASK else result
106def get_cell_index3(entry: int) -> int:
107 """Third cell index; returns -1 if not present."""
108 if entry < 0:
109 entry = -entry
110 result = (entry >> _INDEX3_OFFSET) & _INDEX_MASK
111 return -1 if result == _INDEX_MASK else result
114def get_candidate(entry: int) -> int:
115 """Candidate digit (bits 0-3)."""
116 if entry < 0:
117 entry = -entry
118 return entry & _CAND_MASK
121def is_strong(entry: int) -> bool:
122 """True if the entry represents a strong link (candidate SET)."""
123 if entry < 0:
124 entry = -entry
125 return (entry & _STRONG_MASK) != 0
128def get_node_type(entry: int) -> int:
129 """Node type: NORMAL_NODE, GROUP_NODE, or ALS_NODE."""
130 if entry < 0:
131 entry = -entry
132 return (entry & _MODE_MASK) >> _MODE_OFFSET
135def get_als_index(entry: int) -> int:
136 """ALS index (14-bit value stored across cell_index2 + cell_index3 fields)."""
137 if entry < 0:
138 entry = -entry
139 return (entry & _ALS_INDEX_MASK) >> _ALS_INDEX_OFFSET
142def get_lower_als_index(als_index: int) -> int:
143 """Lower 7 bits of an ALS index (stored in cell_index2 position)."""
144 return als_index & _INDEX_MASK
147def get_higher_als_index(als_index: int) -> int:
148 """Upper 7 bits of an ALS index (stored in cell_index3 position)."""
149 return (als_index >> 7) & _INDEX_MASK
152def make_entry_als(
153 cell_index: int,
154 als_index: int,
155 candidate: int,
156 is_strong: bool,
157 node_type: int,
158) -> int:
159 """Create an ALS/group node entry by splitting als_index into two 7-bit halves."""
160 return make_entry(
161 cell_index,
162 get_lower_als_index(als_index),
163 get_higher_als_index(als_index),
164 candidate,
165 is_strong,
166 node_type,
167 )
170def replace_als_index(entry: int, new_als_index: int) -> int:
171 """Return a copy of *entry* with the ALS index replaced."""
172 entry &= ~_ALS_INDEX_MASK
173 entry |= (new_als_index << _ALS_INDEX_OFFSET) & _ALS_INDEX_MASK
174 return entry
177def set_strong(entry: int, strong: bool) -> int:
178 """Return a copy of *entry* with the strong flag set or cleared."""
179 if strong:
180 return entry | _STRONG_MASK
181 return entry & ~_STRONG_MASK