summaryrefslogtreecommitdiff
path: root/image
diff options
context:
space:
mode:
authorPiotr Pawlow <pp@siedziba.pl>2017-08-11 15:47:35 +0200
committerDavid Sterba <dsterba@suse.com>2017-09-25 15:17:01 +0200
commit0e88d6d1d39524b77feb36302c6b5e720473270d (patch)
tree4fdc24c95bae079a7bde51dc67c7955cc8f19c9e /image
parent334d83053a593e0adeea7f958a9811381fb458fc (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>
Diffstat (limited to 'image')
-rw-r--r--image/main.c15
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(