diff options
| author | Piotr Pawlow <pp@siedziba.pl> | 2017-08-11 15:47:35 +0200 |
|---|---|---|
| committer | David Sterba <dsterba@suse.com> | 2017-09-25 15:17:01 +0200 |
| commit | 0e88d6d1d39524b77feb36302c6b5e720473270d (patch) | |
| tree | 4fdc24c95bae079a7bde51dc67c7955cc8f19c9e | |
| parent | 334d83053a593e0adeea7f958a9811381fb458fc (diff) | |
btrfs-progs: image: use CRC32C reversing instead of brute force to find collisions
Author: Piotr Pawlow <pp@siedziba.pl>
Signed-off-by: David Sterba <dsterba@suse.com>
| -rw-r--r-- | image/main.c | 15 |
1 files changed, 12 insertions, 3 deletions
diff --git a/image/main.c b/image/main.c index c743cb4d..4cffbdba 100644 --- a/image/main.c +++ b/image/main.c @@ -447,17 +447,26 @@ static int find_collision_is_suffix_valid(const char *suffix) return 1; } -static int find_collision_brute_force(struct name *val, u32 name_len) +static int find_collision_reverse_crc32c(struct name *val, u32 name_len) { unsigned long checksum; + unsigned long current_checksum; int found = 0; int i; + /* There are no same length collisions of 4 or less bytes */ + if (name_len <= 4) + return 0; checksum = crc32c(~1, val->val, name_len); + name_len -= 4; memset(val->sub, ' ', name_len); i = 0; while (1) { - if (crc32c(~1, val->sub, name_len) == checksum && + current_checksum = crc32c(~1, val->sub, name_len); + find_collision_calc_suffix(current_checksum, + checksum, + val->sub + name_len); + if (find_collision_is_suffix_valid(val->sub + name_len) && memcmp(val->sub, val->val, val->len)) { found = 1; break; @@ -524,7 +533,7 @@ static char *find_collision(struct metadump_struct *md, char *name, return NULL; } - found = find_collision_brute_force(val, name_len); + found = find_collision_reverse_crc32c(val, name_len); if (!found) { warning( |