Whole file
eerimoq/bincopy
The author described this change as “Fix: Merge adjacent segments when fast inserting.”. It counts as a record because the check below fails on the code as it stood at bb6cb6054 and passes on 6ff05a3db, with nothing else changed between the two runs.
Projecteerimoq/bincopy
Fix saved2017-09-18
Sharing licenceMIT · LICENSE
Change size+671 −671
What the code was meant to do, written into the code itself as a save note
Fix: Merge adjacent segments when fast inserting.
The change
| 17 | 17 | ||
| 18 | 18 | ||
| 19 | 19 | __author__ = 'Erik Moqvist' | |
| 20 | - | __version__ = '7.5.0' | |
| 21 | - | ||
| 22 | - | ||
| 23 | - | DEFAULT_WORD_SIZE_BITS = 8 | |
| 24 | - | ||
| 25 | - | ||
| 26 | - | class Error(Exception): | |
| 27 | - | """Bincopy base exception. | |
| 28 | - | ||
| 29 | - | """ | |
| 30 | - | ||
| 31 | - | pass | |
| 32 | - | ||
| 33 | - | ||
| 34 | - | def crc_srec(hexstr): | |
| 35 | - | """Calculate the CRC for given Motorola S-Record hexstring. | |
| 36 | - | ||
| 37 | - | """ | |
| 38 | - | ||
| 39 | - | crc = sum(bytearray(binascii.unhexlify(hexstr))) | |
| 40 | - | crc &= 0xff | |
| 41 | - | crc ^= 0xff | |
| 42 | - | ||
| 43 | - | return crc | |
| 44 | - | ||
| 45 | - | ||
| 46 | - | def crc_ihex(hexstr): | |
| 47 | - | """Calculate crc for given Intel HEX hexstring. | |
| 48 | - | ||
| 49 | - | """ | |
| 50 | - | ||
| 51 | - | crc = sum(bytearray(binascii.unhexlify(hexstr))) | |
| 52 | - | crc &= 0xff | |
| 53 | - | crc = ((~crc + 1) & 0xff) | |
| 54 | - | ||
| 55 | - | return crc | |
| 56 | - | ||
| 57 | - | ||
| 58 | - | def pack_srec(type_, address, size, data): | |
| 59 | - | """Create a Motorola S-Record record of given data. | |
| 60 | - | ||
| 61 | - | """ | |
| 62 | - | ||
| 63 | - | if type_ in '0159': | |
| 64 | - | line = '%02X%04X' % (size + 2 + 1, address) | |
| 65 | - | elif type_ in '268': | |
| 66 | - | line = '%02X%06X' % (size + 3 + 1, address) | |
| 67 | - | elif type_ in '37': | |
| 68 | - | line = '%02X%08X' % (size + 4 + 1, address) | |
| 69 | - | else: | |
| 70 | - | raise Error("expected record type 0..3 or 5..9, but got '{}'".format( | |
| 71 | - | type_)) | |
| 72 | - | ||
| 73 | - | if data: | |
| 74 | - | line += binascii.hexlify(data).decode('utf-8').upper() | |
| 75 | - | ||
| 76 | - | return 'S%s%s%02X' % (type_, line, crc_srec(line)) | |
| 77 | - | ||
| 78 | - | ||
| 79 | - | def unpack_srec(record): | |
| 80 | - | """Unpack given Motorola S-Record record into variables. | |
| 81 | - | ||
| 82 | - | """ | |
| 83 | - | ||
| 84 | - | if len(record) < 6: | |
| 85 | - | raise Error("record '{}' too short".format(record)) | |
| 86 | - | ||
| 87 | - | if record[0] != 'S': | |
| 88 | - | raise Error("record '{}' not starting with an 'S'".format( | |
| 89 | - | record)) | |
| 90 | - | ||
| 91 | - | size = int(record[2:4], 16) | |
| 92 | - | type_ = record[1:2] | |
| 93 | - | ||
| 94 | - | if type_ in '0159': | |
| 95 | - | width = 4 | |
| 96 | - | elif type_ in '268': | |
| 97 | - | width = 6 | |
| 98 | - | elif type_ in '37': | |
| 99 | - | width = 8 | |
| 100 | - | else: | |
| 101 | - | raise Error("expected record type 0..3 or 5..9, but got '{}'".format( | |
| 102 | - | type_)) | |
| 103 | - | ||
| 104 | - | address = int(record[4:4+width], 16) | |
| 105 | - | data = binascii.unhexlify(record[4 + width:4 + 2 * size - 2]) | |
| 106 | - | actual_crc = int(record[4 + 2 * size - 2:], 16) | |
| 107 | - | expected_crc = crc_srec(record[2:4 + 2 * size - 2]) | |
| 108 | - | ||
| 109 | - | if actual_crc != expected_crc: | |
| 110 | - | raise Error("expected crc {:#02x} in record {}, but got {:#02x}".format( | |
| 111 | - | expected_crc, | |
| 112 | - | record, | |
| 113 | - | actual_crc)) | |
| 114 | - | ||
| 115 | - | return (type_, address, size - 1 - width // 2, data) | |
| 116 | - | ||
| 117 | - | ||
| 118 | - | def pack_ihex(type_, address, size, data): | |
| 119 | - | """Create a Intel HEX record of given data. | |
| 120 | - | ||
| 121 | - | """ | |
| 122 | - | ||
| 123 | - | line = '%02X%04X%02X' % (size, address, type_) | |
| 124 | - | ||
| 125 | - | if data: | |
| 126 | - | line += binascii.hexlify(data).decode('utf-8').upper() | |
| 127 | - | ||
| 128 | - | return ':%s%02X' % (line, crc_ihex(line)) | |
| 129 | - | ||
| 130 | - | ||
| 131 | - | def unpack_ihex(record): | |
| 132 | - | """Unpack given Intel HEX record into variables. | |
| 133 | - | ||
| 134 | - | """ | |
| 135 | - | ||
| 136 | - | if len(record) < 11: | |
| 137 | - | raise Error("record '{}' too short".format(record)) | |
| 138 | - | ||
| 139 | - | if record[0] != ':': | |
| 140 | - | raise Error("record '{}' not starting with a ':'".format(record)) | |
| 141 | - | ||
| 142 | - | size = int(record[1:3], 16) | |
| 143 | - | address = int(record[3:7], 16) | |
| 144 | - | type_ = int(record[7:9], 16) | |
| 145 | - | ||
| 146 | - | if size > 0: | |
| 147 | - | data = binascii.unhexlify(record[9:9 + 2 * size]) | |
| 148 | - | else: | |
| 149 | - | data = '' | |
| 150 | - | ||
| 151 | - | actual_crc = int(record[9 + 2 * size:], 16) | |
| 152 | - | expected_crc = crc_ihex(record[1:9 + 2 * size]) | |
| 153 | - | ||
| 154 | - | if actual_crc != expected_crc: | |
| 155 | - | raise Error("expected crc {:#02x} in record {}, but got {:#02x}".format( | |
| 156 | - | expected_crc, | |
| 157 | - | record, | |
| 158 | - | actual_crc)) | |
| 159 | - | ||
| 160 | - | return (type_, address, size, data) | |
| 161 | - | ||
| 162 | - | ||
| 163 | - | def is_srec(records): | |
| 164 | - | try: | |
| 165 | - | unpack_srec(records.splitlines()[0]) | |
| 166 | - | except Error: | |
| 167 | - | return False | |
| 168 | - | else: | |
| 169 | - | return True | |
| 170 | - | ||
| 171 | - | ||
| 172 | - | def is_ihex(records): | |
| 173 | - | try: | |
| 174 | - | unpack_ihex(records.splitlines()[0]) | |
| 175 | - | except Error: | |
| 176 | - | return False | |
| 177 | - | else: | |
| 178 | - | return True | |
| 179 | - | ||
| 180 | - | ||
| 181 | - | class _Segment(object): | |
| 182 | - | """A segment is a chunk data with given minimum and maximum address. | |
| 183 | - | ||
| 184 | - | """ | |
| 185 | - | ||
| 186 | - | def __init__(self, minimum_address, maximum_address, data): | |
| 187 | - | self.minimum_address = minimum_address | |
| 188 | - | self.maximum_address = maximum_address | |
| 189 | - | self.data = data | |
| 190 | - | ||
| 191 | - | def add_data(self, minimum_address, maximum_address, data, overwrite): | |
| 192 | - | """Add given data to this segment. The added data must be adjecent to | |
| 193 | - | the current segment data, otherwise an exception is thrown. | |
| 194 | - | ||
| 195 | - | """ | |
| 196 | - | ||
| 197 | - | if minimum_address == self.maximum_address: | |
| 198 | - | self.maximum_address = maximum_address | |
| 199 | - | self.data += data | |
| 200 | - | elif maximum_address == self.minimum_address: | |
| 201 | - | self.minimum_address = minimum_address | |
| 202 | - | self.data = data + self.data | |
| 203 | - | elif (overwrite | |
| 204 | - | and minimum_address < self.maximum_address | |
| 205 | - | and maximum_address > self.minimum_address): | |
| 206 | - | self_data_offset = minimum_address - self.minimum_address | |
| 207 | - | ||
| 208 | - | # prepend data | |
| 209 | - | if self_data_offset < 0: | |
| 210 | - | self_data_offset *= -1 | |
| 211 | - | self.data = data[:self_data_offset] + self.data | |
| 212 | - | del data[:self_data_offset] | |
| 213 | - | self.minimum_address = minimum_address | |
| 214 | - | ||
| 215 | - | # overwrite overlapping part | |
| 216 | - | self_data_left = len(self.data) - self_data_offset | |
| 217 | - | ||
| 218 | - | if len(data) <= self_data_left: | |
| 219 | - | self.data[self_data_offset:self_data_offset + len(data)] = data | |
| 220 | - | data = bytearray() | |
| 221 | - | else: | |
| 222 | - | self.data[self_data_offset:] = data[:self_data_left] | |
| 223 | - | data = data[self_data_left:] | |
| 224 | - | ||
| 225 | - | # append data | |
| 226 | - | if len(data) > 0: | |
| 227 | - | self.data += data | |
| 228 | - | self.maximum_address = maximum_address | |
| 229 | - | else: | |
| 230 | - | raise Error('data added to a segment must be adjacent to or ' | |
| 231 | - | 'overlapping with the original segment data') | |
| 232 | - | ||
| 233 | - | def remove_data(self, minimum_address, maximum_address): | |
| 234 | - | """Remove given data range from this segment. Returns the second | |
| 235 | - | segment if the removed data splits this segment in two. | |
| 236 | - | ||
| 237 | - | """ | |
| 238 | - | ||
| 239 | - | if ((minimum_address >= self.maximum_address) | |
| 240 | - | and (maximum_address <= self.minimum_address)): | |
| 241 | - | raise Error('cannot remove data that is not part of the segment') | |
| 242 | - | ||
| 243 | - | if minimum_address < self.minimum_address: | |
| 244 | - | minimum_address = self.minimum_address | |
| 245 | - | ||
| 246 | - | if maximum_address > self.maximum_address: | |
| 247 | - | maximum_address = self.maximum_address | |
| 248 | - | ||
| 249 | - | remove_size = maximum_address - minimum_address | |
| 250 | - | part1_size = minimum_address - self.minimum_address | |
| 251 | - | part1_data = self.data[0:part1_size] | |
| 252 | - | part2_data = self.data[part1_size + remove_size:] | |
| 253 | - | ||
| 254 | - | if len(part1_data) and len(part2_data): | |
| 255 | - | # Update this segment and return the second segment. | |
| 256 | - | self.maximum_address = self.minimum_address + part1_size | |
| 257 | - | self.data = part1_data | |
| 258 | - | ||
| 259 | - | return _Segment(maximum_address, | |
| 260 | - | maximum_address + len(part2_data), | |
| 261 | - | part2_data) | |
| 262 | - | else: | |
| 263 | - | # Update this segment. | |
| 264 | - | if len(part1_data) > 0: | |
| 265 | - | self.maximum_address = minimum_address | |
| 266 | - | self.data = part1_data | |
| 267 | - | elif len(part2_data) > 0: | |
| 268 | - | self.minimum_address = maximum_address | |
| 269 | - | self.data = part2_data | |
| 270 | - | else: | |
| 271 | - | self.maximum_address = self.minimum_address | |
| 272 | - | self.data = bytearray() | |
| 273 | - | ||
| 274 | - | def __str__(self): | |
| 275 | - | return '[%#x .. %#x]: %s' % (self.minimum_address, | |
| 276 | - | self.maximum_address, | |
| 277 | - | binascii.hexlify(self.data)) | |
| 278 | - | ||
| 279 | - | ||
| 280 | - | class _Segments(object): | |
| 281 | - | """A list of segments. | |
| 282 | - | ||
| 283 | - | """ | |
| 284 | - | ||
| 285 | - | def __init__(self): | |
| 286 | - | self.current_segment = None | |
| 287 | - | self.current_segment_index = None | |
| 288 | - | self.list = [] | |
| 289 | - | ||
| 290 | - | def add(self, segment, overwrite=False): | |
| 291 | - | """Add segments by ascending address. | |
| 292 | - | ||
| 293 | - | """ | |
| 294 | - | ||
| 295 | - | if self.list: | |
| 296 | - | if segment.minimum_address == self.current_segment.maximum_address: | |
| 297 | - | # fast insertion for adjecent segments | |
| 298 | - | self.current_segment.add_data(segment.minimum_address, | |
| 299 | - | segment.maximum_address, | |
| 300 | - | segment.data, | |
| 301 | - | overwrite) | |
| 302 | - | else: | |
| 303 | - | # linear insert | |
| 304 | - | for i, s in enumerate(self.list): | |
| 305 | - | if segment.minimum_address <= s.maximum_address: | |
| 306 | - | break | |
| 307 | - | ||
| 308 | - | if segment.minimum_address > s.maximum_address: | |
| 309 | - | # non-overlapping, non-adjacent after | |
| 310 | - | self.list.append(segment) | |
| 311 | - | elif segment.maximum_address < s.minimum_address: | |
| 312 | - | # non-overlapping, non-adjacent before | |
| 313 | - | self.list.insert(i, segment) | |
| 314 | - | else: | |
| 315 | - | # adjacent or overlapping | |
| 316 | - | s.add_data(segment.minimum_address, | |
| 317 | - | segment.maximum_address, | |
| 318 | - | segment.data, | |
| 319 | - | overwrite) | |
| 320 | - | segment = s | |
| 321 | - | ||
| 322 | - | self.current_segment = segment | |
| 323 | - | self.current_segment_index = i | |
| 324 | - | ||
| 325 | - | # remove overwritten and merge adjacent segments | |
| 326 | - | while self.current_segment is not self.list[-1]: | |
| 327 | - | s = self.list[self.current_segment_index + 1] | |
| 328 | - | ||
| 329 | - | if self.current_segment.maximum_address >= s.maximum_address: | |
| 330 | - | # the whole segment is overwritten | |
| 331 | - | del self.list[self.current_segment_index + 1] | |
| 332 | - | elif self.current_segment.maximum_address > s.minimum_address: | |
| 333 | - | # beginning of the segment overwritten | |
| 334 | - | self.current_segment.add_data( | |
| 335 | - | self.current_segment.maximum_address, | |
| 336 | - | s.maximum_address, | |
| 337 | - | s.data[self.current_segment.maximum_address - s.minimum_address:], | |
| 338 | - | overwrite=False) | |
| 339 | - | del self.list[self.current_segment_index+1] | |
| 340 | - | break | |
| 341 | - | else: | |
| 342 | - | # segments are not overlapping | |
| 343 | - | break | |
| 344 | - | else: | |
| 345 | - | self.list.append(segment) | |
| 346 | - | self.current_segment = segment | |
| 347 | - | self.current_segment_index = 0 | |
| 348 | - | ||
| 349 | - | def remove(self, minimum_address, maximum_address): | |
| 350 | - | new_list = [] | |
| 351 | - | ||
| 352 | - | for segment in self.list: | |
| 353 | - | if (segment.maximum_address <= minimum_address | |
| 354 | - | or maximum_address < segment.minimum_address): | |
| 355 | - | # no overlap | |
| 356 | - | new_list.append(segment) | |
| 357 | - | else: | |
| 358 | - | # overlapping, remove overwritten parts segments | |
| 359 | - | split = segment.remove_data(minimum_address, maximum_address) | |
| 360 | - | ||
| 361 | - | if segment.minimum_address < segment.maximum_address: | |
| 362 | - | new_list.append(segment) | |
| 363 | - | ||
| 364 | - | if split: | |
| 365 | - | new_list.append(split) | |
| 366 | - | ||
| 367 | - | self.list = new_list | |
| 368 | - | ||
| 369 | - | def iter(self, size=32): | |
| 370 | - | """Iterate over all segments and return chunks of the data. | |
| 371 | - | ||
| 372 | - | """ | |
| 373 | - | ||
| 374 | - | for segment in self.list: | |
| 375 | - | data = segment.data | |
| 376 | - | address = segment.minimum_address | |
| 377 | - | ||
| 378 | - | for offset in range(0, len(data), size): | |
| 379 | - | yield address + offset, data[offset:offset + size] | |
| 380 | - | ||
| 381 | - | def get_minimum_address(self): | |
| 382 | - | """Get the minimum address of the data. | |
| 383 | - | ||
| 384 | - | """ | |
| 385 | - | ||
| 386 | - | if not self.list: | |
| 387 | - | raise Error('cannot get minimum address from an empty file') | |
| 388 | - | ||
| 389 | - | return self.list[0].minimum_address | |
| 390 | - | ||
| 391 | - | def get_maximum_address(self): | |
| 392 | - | """Get the maximum address of the data. | |
| 393 | - | ||
| 394 | - | """ | |
| 395 | - | ||
| 396 | - | if not self.list: | |
| 397 | - | raise Error('cannot get maximum address from an empty file') | |
| 398 | - | ||
| 399 | - | return self.list[-1].maximum_address | |
| 400 | - | ||
| 401 | - | def get_size(self): | |
| 402 | - | """Get the size of the binary, including holes in the data. | |
| 403 | - | ||
| 404 | - | """ | |
| 405 | - | ||
| 406 | - | if not self.list: | |
| 407 | - | return 0 | |
| 408 | - | ||
| 409 | - | return self.get_maximum_address() - self.get_minimum_address() | |
| 410 | - | ||
| 411 | - | def __str__(self): | |
| 412 | - | return '\n'.join([s.__str__() for s in self.list]) | |
| 413 | - | ||
| 414 | - | ||
| 415 | - | class BinFile(object): | |
| 416 | - | ||
| 948 further changed lines not shown | |||
The check that tells the two apart
fail→pass·tests/test_bincopy.py::BinCopyTest::test_non_sorted_segments
Check file tests/test_bincopy.py, taken without changes from the fix and copied onto the older code, so the exact same check runs against both versions.
Origin and history
The code before itbb6cb605437ed26e7321bbc7bee81d213eb19c8a
Broken version dated2017-09-18
Modulebincopy
Units changedBinFile, _Segment, _Segments
Fingerprint90d66113c402a3ee
Checked2026-08-18 by goldset/0.1
Every field above is generated by our program. None of it is written by hand.