Coverage for src / tracekit / search / pattern.py: 100%

1"""Pattern search in digital traces. 

2 

3 

4This module provides efficient bit pattern matching in digital signals 

5with wildcard support via mask parameter. 

6""" 

7 

8from typing import cast 

9 

10import numpy as np 

11from numpy.typing import NDArray 

12 

13 

14def find_pattern( 

15 trace: NDArray[np.float64] | NDArray[np.uint8], 

16 pattern: int | NDArray[np.uint8], 

17 mask: int | NDArray[np.uint8] | None = None, 

18 *, 

19 threshold: float | None = None, 

20 min_spacing: int = 1, 

21) -> list[tuple[int, NDArray[np.uint8]]]: 

22 """Find occurrences of bit patterns in digital traces. 

23 

24 : Pattern search with wildcard support via mask. 

25 Works on both raw analog traces (with threshold) and decoded digital data. 

26 

27 Args: 

28 trace: Input trace array. If analog (float), threshold is required. 

29 If already digital (uint8), threshold is ignored. 

30 pattern: Bit pattern to search for. Can be: 

31 - Integer: e.g., 0b10101010 (8-bit pattern) 

32 - Array: sequence of bytes to match 

33 mask: Optional mask for wildcard matching. Bits set to 0 in mask 

34 are "don't care" positions. Can be: 

35 - Integer: e.g., 0xFF (all bits matter) 

36 - Array: per-byte masks 

37 If None, all bits must match (equivalent to all 1s). 

38 threshold: Threshold for converting analog to digital (required if 

39 trace is analog). Typically mid-level of logic family. 

40 min_spacing: Minimum samples between detected patterns to avoid 

41 overlapping matches (default: 1) 

42 

43 Returns: 

44 List of (index, match) tuples where: 

45 - index: Starting sample index of the pattern 

46 - match: The actual matched bit sequence as uint8 array 

47 

48 Raises: 

49 ValueError: If analog trace provided without threshold 

50 ValueError: If pattern is empty 

51 

52 Examples: 

53 >>> # Find 0xAA pattern in analog trace 

54 >>> import numpy as np 

55 >>> trace = np.array([0, 1, 0, 1, 0, 1, 0, 1, 0, 0]) 

56 >>> matches = find_pattern(trace, 0b10101010, threshold=0.5) 

57 >>> print(f"Found {len(matches)} matches") 

58 

59 >>> # Wildcard search: find 0b1010xxxx (x = don't care) 

60 >>> pattern = 0b10100000 

61 >>> mask = 0b11110000 # Only upper 4 bits matter 

62 >>> matches = find_pattern(trace, pattern, mask, threshold=0.5) 

63 

64 >>> # Search in already-decoded digital data 

65 >>> digital = np.array([0xAA, 0x55, 0xAA, 0x00], dtype=np.uint8) 

66 >>> matches = find_pattern(digital, 0xAA) 

67 

68 Notes: 

69 - For analog traces, values >= threshold are interpreted as '1' 

70 - Mask bits: 1 = must match, 0 = don't care 

71 - Overlapping patterns can be filtered with min_spacing > 1 

72 - Returns empty list if no matches found 

73 

74 References: 

75 SRCH-001: Pattern Search 

76 """ 

77 if trace.size == 0: 

78 return [] 

79 

80 # Convert pattern to array if integer 

81 if isinstance(pattern, int): 

82 if pattern < 0: 

83 raise ValueError("Pattern must be non-negative") 

84 # Convert to byte array (variable length based on value) 

85 pattern_bytes = [] 

86 if pattern == 0: 

87 pattern_bytes = [0] 

88 else: 

89 temp = pattern 

90 while temp > 0: 

91 pattern_bytes.insert(0, temp & 0xFF) 

92 temp >>= 8 

93 pattern_arr = np.array(pattern_bytes, dtype=np.uint8) 

94 else: 

95 pattern_arr = np.asarray(pattern, dtype=np.uint8) 

96 

97 if pattern_arr.size == 0: 

98 raise ValueError("Pattern cannot be empty") 

99 

100 # Convert mask to array if integer 

101 if mask is not None: 

102 if isinstance(mask, int): 

103 mask_bytes: list[int] = [] 

104 temp = mask 

105 # Match pattern length 

106 for _ in range(len(pattern_arr)): 

107 mask_bytes.insert(0, temp & 0xFF) 

108 temp >>= 8 

109 mask_arr = np.array(mask_bytes, dtype=np.uint8) 

110 else: 

111 mask_arr = np.asarray(mask, dtype=np.uint8) 

112 

113 # Ensure mask and pattern have same length 

114 if mask_arr.size != pattern_arr.size: 

115 raise ValueError("Mask and pattern must have same length") 

116 else: 

117 # Default: all bits matter 

118 mask_arr = np.full(pattern_arr.size, 0xFF, dtype=np.uint8) 

119 

120 # Convert analog trace to digital if needed 

121 if trace.dtype != np.uint8: 

122 if threshold is None: 

123 raise ValueError( 

124 "Threshold required for analog trace conversion. " 

125 "Provide threshold parameter or pre-convert to digital." 

126 ) 

127 # Simple threshold conversion: >= threshold is 1 

128 digital = (trace >= threshold).astype(np.uint8) 

129 # Pack bits into bytes (8 samples per byte) 

130 # Pad to multiple of 8 

131 n_pad = (8 - len(digital) % 8) % 8 

132 if n_pad: 

133 digital = np.pad(digital, (0, n_pad), constant_values=0) 

134 # Pack bits 

135 digital_packed: NDArray[np.uint8] = np.packbits(digital, bitorder="big") 

136 else: 

137 digital_packed = cast("NDArray[np.uint8]", trace) 

138 

139 if digital_packed.size < pattern_arr.size: 

140 return [] 

141 

142 # Sliding window pattern matching with mask 

143 matches: list[tuple[int, NDArray[np.uint8]]] = [] 

144 i = 0 

145 

146 while i <= len(digital_packed) - len(pattern_arr): 

147 window = digital_packed[i : i + len(pattern_arr)] 

148 

149 # Apply mask and compare 

150 masked_window = window & mask_arr 

151 masked_pattern = pattern_arr & mask_arr 

152 

153 if np.array_equal(masked_window, masked_pattern): 

154 matches.append((i, window.copy())) 

155 # Skip ahead by min_spacing to avoid overlapping matches 

156 i += max(1, min_spacing) 

157 else: 

158 i += 1 

159 

160 return matches