diff options
| -rw-r--r-- | rolling-hash-2d.c | 24 |
1 files changed, 15 insertions, 9 deletions
diff --git a/rolling-hash-2d.c b/rolling-hash-2d.c index 98417a6..c8968cd 100644 --- a/rolling-hash-2d.c +++ b/rolling-hash-2d.c @@ -128,7 +128,8 @@ block_hash(const char *filename, struct frame *prev) height = cairo_image_surface_get_height(frame->surface); stride = cairo_image_surface_get_stride(frame->surface); - frame->block_count = width * height / (size * size); + frame->block_count = + ((width + size - 1) / size) * ((height + size - 1) / size); frame->length = 1 << (31 - __builtin_clz(frame->block_count * 4)); frame->shift = __builtin_clz(frame->length) + 1; printf("image %s, %dx%d, %d 32x32 blocks, %d hash table " @@ -145,7 +146,7 @@ block_hash(const char *filename, struct frame *prev) frame->length * sizeof frame->hash_table[0]); memset(stats, 0, sizeof stats); - skyline = malloc(width * sizeof skyline[0]); + skyline = malloc((width + size) * sizeof skyline[0]); memset(skyline, 0, width * sizeof skyline[0]); end_prime = 1; @@ -161,9 +162,9 @@ block_hash(const char *filename, struct frame *prev) block_hashes[j] = 0; x0 = 0; - x1 = width - size; + x1 = width; y0 = 0; - y1 = height - size; + y1 = height; #if 0 if (prev) { x0 = 200; @@ -181,8 +182,9 @@ block_hash(const char *filename, struct frame *prev) for (j = x0; j < x1; j++) { block_hashes[j] = block_hashes[j] * vprime + hash; - hash = hash * prime + line[j + size] - - line[j] * end_prime; + hash = hash * prime - line[j] * end_prime; + if (j + size < width) + hash += line[j + size]; } } @@ -194,7 +196,8 @@ block_hash(const char *filename, struct frame *prev) top_hash = 0; skyline_pixels = 0; for (j = x0; j < x0 + size; j++) { - hash = hash * prime + line[j]; + if (i + size < height) + hash = hash * prime + line[j]; top_hash = top_hash * prime + top[j]; if (i < skyline[j]) @@ -261,8 +264,11 @@ block_hash(const char *filename, struct frame *prev) block_hashes[j] * vprime + hash - top_hash * end_vprime; - hash = hash * prime + line[j + size] - - line[j] * end_prime; + if (i + size < height) { + hash = hash * prime - line[j] * end_prime; + if (j + size < width) + hash += line[j + size]; + } top_hash = top_hash * prime + top[j + size] - top[j] * end_prime; } |