blob: e3f519bec6e86a086bacb51491705c37bf222546 [file] [log] [blame]
Urvang Joshid538cea2013-09-12 13:41:09 -07001// Copyright 2013 Google Inc. All Rights Reserved.
2//
3// Use of this source code is governed by a BSD-style license
4// that can be found in the COPYING file in the root of the source
5// tree. An additional intellectual property rights grant can be found
6// in the file PATENTS. All contributing project authors may
7// be found in the AUTHORS file in the root of the source tree.
8// -----------------------------------------------------------------------------
9//
10// Helper structs and methods for gif2webp tool.
11//
12
13#include <assert.h>
14#include <stdio.h>
15
16#include "webp/encode.h"
17#include "./gif2webp_util.h"
18
19#define DELTA_INFINITY 1ULL << 32
20#define KEYFRAME_NONE -1
21
22//------------------------------------------------------------------------------
Urvang Joshi38efdc22013-10-14 14:39:46 -070023// Helper utilities.
Urvang Joshid538cea2013-09-12 13:41:09 -070024
25static void ClearRectangle(WebPPicture* const picture,
26 int left, int top, int width, int height) {
27 int j;
28 for (j = top; j < top + height; ++j) {
29 uint32_t* const dst = picture->argb + j * picture->argb_stride;
30 int i;
31 for (i = left; i < left + width; ++i) {
Urvang Joshi38efdc22013-10-14 14:39:46 -070032 dst[i] = WEBP_UTIL_TRANSPARENT_COLOR;
Urvang Joshid538cea2013-09-12 13:41:09 -070033 }
34 }
35}
36
Urvang Joshid538cea2013-09-12 13:41:09 -070037void WebPUtilClearPic(WebPPicture* const picture,
38 const WebPFrameRect* const rect) {
39 if (rect != NULL) {
40 ClearRectangle(picture, rect->x_offset, rect->y_offset,
41 rect->width, rect->height);
42 } else {
43 ClearRectangle(picture, 0, 0, picture->width, picture->height);
44 }
45}
46
47// TODO: Also used in picture.c. Move to a common location?
48// Copy width x height pixels from 'src' to 'dst' honoring the strides.
49static void CopyPlane(const uint8_t* src, int src_stride,
50 uint8_t* dst, int dst_stride, int width, int height) {
51 while (height-- > 0) {
52 memcpy(dst, src, width);
53 src += src_stride;
54 dst += dst_stride;
55 }
56}
57
Urvang Joshi38efdc22013-10-14 14:39:46 -070058// Copy pixels from 'src' to 'dst' honoring strides. 'src' and 'dst' are assumed
59// to be already allocated.
60static void CopyPixels(const WebPPicture* const src, WebPPicture* const dst) {
Urvang Joshid538cea2013-09-12 13:41:09 -070061 assert(src->width == dst->width && src->height == dst->height);
62 CopyPlane((uint8_t*)src->argb, 4 * src->argb_stride, (uint8_t*)dst->argb,
63 4 * dst->argb_stride, 4 * src->width, src->height);
64}
65
Urvang Joshi38efdc22013-10-14 14:39:46 -070066// Given 'src' picture and its frame rectangle 'rect', blend it into 'dst'.
67static void BlendPixels(const WebPPicture* const src,
68 const WebPFrameRect* const rect,
69 WebPPicture* const dst) {
Urvang Joshid538cea2013-09-12 13:41:09 -070070 int j;
71 assert(src->width == dst->width && src->height == dst->height);
72 for (j = rect->y_offset; j < rect->y_offset + rect->height; ++j) {
73 int i;
74 for (i = rect->x_offset; i < rect->x_offset + rect->width; ++i) {
75 const uint32_t src_pixel = src->argb[j * src->argb_stride + i];
76 const int src_alpha = src_pixel >> 24;
77 if (src_alpha != 0) {
78 dst->argb[j * dst->argb_stride + i] = src_pixel;
79 }
80 }
81 }
82}
83
Urvang Joshi38efdc22013-10-14 14:39:46 -070084// Replace transparent pixels within 'dst_rect' of 'dst' by those in the 'src'.
85static void ReduceTransparency(const WebPPicture* const src,
86 const WebPFrameRect* const rect,
87 WebPPicture* const dst) {
skal00125192013-10-08 15:04:52 +020088 int i, j;
89 assert(src != NULL && dst != NULL && rect != NULL);
Urvang Joshi606c4302013-09-30 16:48:39 -070090 assert(src->width == dst->width && src->height == dst->height);
91 for (j = rect->y_offset; j < rect->y_offset + rect->height; ++j) {
Urvang Joshi606c4302013-09-30 16:48:39 -070092 for (i = rect->x_offset; i < rect->x_offset + rect->width; ++i) {
93 const uint32_t src_pixel = src->argb[j * src->argb_stride + i];
94 const int src_alpha = src_pixel >> 24;
95 const uint32_t dst_pixel = dst->argb[j * dst->argb_stride + i];
96 const int dst_alpha = dst_pixel >> 24;
97 if (dst_alpha == 0 && src_alpha == 0xff) {
98 dst->argb[j * dst->argb_stride + i] = src_pixel;
99 }
100 }
101 }
102}
103
Urvang Joshi38efdc22013-10-14 14:39:46 -0700104// Replace similar blocks of pixels by a 'see-through' transparent block
105// with uniform average color.
106static void FlattenSimilarBlocks(const WebPPicture* const src,
107 const WebPFrameRect* const rect,
108 WebPPicture* const dst) {
skal00125192013-10-08 15:04:52 +0200109 int i, j;
110 const int block_size = 8;
111 const int y_start = (rect->y_offset + block_size) & ~(block_size - 1);
112 const int y_end = (rect->y_offset + rect->height) & ~(block_size - 1);
113 const int x_start = (rect->x_offset + block_size) & ~(block_size - 1);
114 const int x_end = (rect->x_offset + rect->width) & ~(block_size - 1);
115 assert(src != NULL && dst != NULL && rect != NULL);
116 assert(src->width == dst->width && src->height == dst->height);
117 assert((block_size & (block_size - 1)) == 0); // must be a power of 2
118 // Iterate over each block and count similar pixels.
119 for (j = y_start; j < y_end; j += block_size) {
120 for (i = x_start; i < x_end; i += block_size) {
121 int cnt = 0;
122 int avg_r = 0, avg_g = 0, avg_b = 0;
123 int x, y;
124 const uint32_t* const psrc = src->argb + j * src->argb_stride + i;
125 uint32_t* const pdst = dst->argb + j * dst->argb_stride + i;
126 for (y = 0; y < block_size; ++y) {
127 for (x = 0; x < block_size; ++x) {
128 const uint32_t src_pixel = psrc[x + y * src->argb_stride];
129 const int alpha = src_pixel >> 24;
130 if (alpha == 0xff &&
131 src_pixel == pdst[x + y * dst->argb_stride]) {
132 ++cnt;
133 avg_r += (src_pixel >> 16) & 0xff;
134 avg_g += (src_pixel >> 8) & 0xff;
135 avg_b += (src_pixel >> 0) & 0xff;
136 }
137 }
138 }
139 // If we have a fully similar block, we replace it with an
140 // average transparent block. This compresses better in lossy mode.
141 if (cnt == block_size * block_size) {
142 const uint32_t color = (0x00 << 24) |
143 ((avg_r / cnt) << 16) |
144 ((avg_g / cnt) << 8) |
145 ((avg_b / cnt) << 0);
146 for (y = 0; y < block_size; ++y) {
147 for (x = 0; x < block_size; ++x) {
148 pdst[x + y * dst->argb_stride] = color;
149 }
150 }
151 }
152 }
153 }
154}
155
Urvang Joshid538cea2013-09-12 13:41:09 -0700156//------------------------------------------------------------------------------
157// Key frame related utilities.
158
Urvang Joshi38efdc22013-10-14 14:39:46 -0700159// Returns true if 'curr' frame with frame rectangle 'curr_rect' is a key frame,
160// that is, it can be decoded independently of 'prev' canvas.
161static int IsKeyFrame(const WebPPicture* const curr,
162 const WebPFrameRect* const curr_rect,
163 const WebPPicture* const prev) {
Urvang Joshid538cea2013-09-12 13:41:09 -0700164 int i, j;
165 int is_key_frame = 1;
166
167 // If previous canvas (with previous frame disposed) is all transparent,
168 // current frame is a key frame.
169 for (i = 0; i < prev->width; ++i) {
170 for (j = 0; j < prev->height; ++j) {
171 const uint32_t prev_alpha = (prev->argb[j * prev->argb_stride + i]) >> 24;
172 if (prev_alpha != 0) {
173 is_key_frame = 0;
174 break;
175 }
176 }
177 if (!is_key_frame) break;
178 }
179 if (is_key_frame) return 1;
180
181 // If current frame covers the whole canvas and does not contain any
182 // transparent pixels that depend on previous canvas, then current frame is
183 // a key frame.
184 if (curr_rect->width == curr->width && curr_rect->height == curr->height) {
185 assert(curr_rect->x_offset == 0 && curr_rect->y_offset == 0);
186 is_key_frame = 1;
187 for (j = 0; j < prev->height; ++j) {
188 for (i = 0; i < prev->width; ++i) {
189 const uint32_t prev_alpha =
190 (prev->argb[j * prev->argb_stride + i]) >> 24;
191 const uint32_t curr_alpha =
192 (curr->argb[j * curr->argb_stride + i]) >> 24;
193 if (curr_alpha != 0xff && prev_alpha != 0) {
194 is_key_frame = 0;
195 break;
196 }
197 }
198 if (!is_key_frame) break;
199 }
200 if (is_key_frame) return 1;
201 }
202
203 return 0;
204}
205
Urvang Joshi38efdc22013-10-14 14:39:46 -0700206// Given 'prev' frame and current frame rectangle 'rect', convert 'curr' frame
207// to a key frame.
208static void ConvertToKeyFrame(const WebPPicture* const prev,
209 WebPFrameRect* const rect,
210 WebPPicture* const curr) {
Urvang Joshid538cea2013-09-12 13:41:09 -0700211 int j;
212 assert(curr->width == prev->width && curr->height == prev->height);
213
214 // Replace transparent pixels of current canvas with those from previous
215 // canvas (with previous frame disposed).
216 for (j = 0; j < curr->height; ++j) {
217 int i;
218 for (i = 0; i < curr->width; ++i) {
219 uint32_t* const curr_pixel = curr->argb + j * curr->argb_stride + i;
220 const int curr_alpha = *curr_pixel >> 24;
221 if (curr_alpha == 0) {
222 *curr_pixel = prev->argb[j * prev->argb_stride + i];
223 }
224 }
225 }
226
227 // Frame rectangle now covers the whole canvas.
228 rect->x_offset = 0;
229 rect->y_offset = 0;
230 rect->width = curr->width;
231 rect->height = curr->height;
232}
233
234//------------------------------------------------------------------------------
Urvang Joshi38efdc22013-10-14 14:39:46 -0700235// Encoded frame.
236
237// Used to store two candidates of encoded data for an animation frame. One of
238// the two will be chosen later.
239typedef struct {
240 WebPMuxFrameInfo sub_frame; // Encoded frame rectangle.
241 WebPMuxFrameInfo key_frame; // Encoded frame if it was converted to keyframe.
242} EncodedFrame;
243
244// Release the data contained by 'encoded_frame'.
245static void FrameRelease(EncodedFrame* const encoded_frame) {
246 WebPDataClear(&encoded_frame->sub_frame.bitstream);
247 WebPDataClear(&encoded_frame->key_frame.bitstream);
248 memset(encoded_frame, 0, sizeof(*encoded_frame));
249}
250
251//------------------------------------------------------------------------------
252// Frame cache.
253
254// Used to store encoded frames that haven't been output yet.
255struct WebPFrameCache {
256 EncodedFrame* encoded_frames; // Array of encoded frames.
257 size_t size; // Number of allocated data elements.
258 size_t start; // Start index.
259 size_t count; // Number of valid data elements.
260 int flush_count; // If >0, ‘flush_count’ frames starting from
261 // 'start' are ready to be added to mux.
262 int64_t best_delta; // min(canvas size - frame size) over the frames.
263 // Can be negative in certain cases due to
264 // transparent pixels in a frame.
265 int keyframe; // Index of selected keyframe relative to 'start'.
266
267 size_t kmin; // Min distance between key frames.
268 size_t kmax; // Max distance between key frames.
269 size_t count_since_key_frame; // Frames seen since the last key frame.
270 WebPPicture prev_canvas; // Previous canvas (properly disposed).
271 WebPPicture curr_canvas; // Current canvas (temporary buffer).
272 int is_first_frame; // True if no frames have been added to the cache
273 // since WebPFrameCacheNew().
274};
275
276// Reset the counters in the cache struct. Doesn't touch 'cache->encoded_frames'
277// and 'cache->size'.
278static void CacheReset(WebPFrameCache* const cache) {
279 cache->start = 0;
280 cache->count = 0;
281 cache->flush_count = 0;
282 cache->best_delta = DELTA_INFINITY;
283 cache->keyframe = KEYFRAME_NONE;
284}
285
286WebPFrameCache* WebPFrameCacheNew(int width, int height,
287 size_t kmin, size_t kmax) {
288 WebPFrameCache* cache = (WebPFrameCache*)malloc(sizeof(*cache));
289 if (cache == NULL) return NULL;
290 CacheReset(cache);
291 cache->is_first_frame = 1;
292
293 // Picture buffers.
294 if (!WebPPictureInit(&cache->prev_canvas) ||
295 !WebPPictureInit(&cache->curr_canvas)) {
296 return NULL;
297 }
298 cache->prev_canvas.width = width;
299 cache->prev_canvas.height = height;
300 cache->prev_canvas.use_argb = 1;
301 if (!WebPPictureAlloc(&cache->prev_canvas) ||
302 !WebPPictureCopy(&cache->prev_canvas, &cache->curr_canvas)) {
303 goto Err;
304 }
305 WebPUtilClearPic(&cache->prev_canvas, NULL);
306
307 // Cache data.
308 cache->kmin = kmin;
309 cache->kmax = kmax;
310 cache->count_since_key_frame = 0;
311 assert(kmax > kmin);
312 cache->size = kmax - kmin;
313 cache->encoded_frames =
314 (EncodedFrame*)calloc(cache->size, sizeof(*cache->encoded_frames));
315 if (cache->encoded_frames == NULL) goto Err;
316
317 return cache; // All OK.
318
319 Err:
320 WebPFrameCacheDelete(cache);
321 return NULL;
322}
323
324void WebPFrameCacheDelete(WebPFrameCache* const cache) {
325 if (cache != NULL) {
326 size_t i;
327 for (i = 0; i < cache->size; ++i) {
328 FrameRelease(&cache->encoded_frames[i]);
329 }
330 free(cache->encoded_frames);
331 WebPPictureFree(&cache->prev_canvas);
332 WebPPictureFree(&cache->curr_canvas);
333 free(cache);
334 }
335}
336
337static int EncodeFrame(const WebPConfig* const config, WebPPicture* const pic,
338 WebPData* const encoded_data) {
339 WebPMemoryWriter memory;
340 pic->use_argb = 1;
341 pic->writer = WebPMemoryWrite;
342 pic->custom_ptr = &memory;
343 WebPMemoryWriterInit(&memory);
344 if (!WebPEncode(config, pic)) {
345 return 0;
346 }
347 encoded_data->bytes = memory.mem;
348 encoded_data->size = memory.size;
349 return 1;
350}
351
352// Returns cached frame at given 'position' index.
353static EncodedFrame* CacheGetFrame(const WebPFrameCache* const cache,
354 size_t position) {
355 assert(cache->start + position < cache->size);
356 return &cache->encoded_frames[cache->start + position];
357}
358
359// Calculate the penalty incurred if we encode given frame as a key frame
360// instead of a sub-frame.
361static int64_t KeyFramePenalty(const EncodedFrame* const encoded_frame) {
362 return ((int64_t)encoded_frame->key_frame.bitstream.size -
363 encoded_frame->sub_frame.bitstream.size);
364}
365
366static int SetFrame(const WebPConfig* const config, int is_key_frame,
367 const WebPPicture* const prev_canvas,
368 WebPPicture* const frame, const WebPFrameRect* const rect,
369 const WebPMuxFrameInfo* const info,
370 WebPPicture* const sub_frame,
371 EncodedFrame* encoded_frame) {
372 WebPMuxFrameInfo* const dst =
373 is_key_frame ? &encoded_frame->key_frame : &encoded_frame->sub_frame;
374 *dst = *info;
375
376 if (!config->lossless && !is_key_frame) {
377 // For lossy compression of a frame, it's better to replace transparent
378 // pixels of 'curr' with actual RGB values, whenever possible.
379 ReduceTransparency(prev_canvas, rect, frame);
380 FlattenSimilarBlocks(prev_canvas, rect, frame);
381 }
382
383 if (!EncodeFrame(config, sub_frame, &dst->bitstream)) {
384 return 0;
385 }
386 return 1;
387}
388
389static void DisposeFrame(WebPMuxAnimDispose dispose_method,
390 const WebPFrameRect* const gif_rect,
391 WebPPicture* const frame, WebPPicture* const canvas) {
392 if (dispose_method == WEBP_MUX_DISPOSE_BACKGROUND) {
393 WebPUtilClearPic(frame, NULL);
394 WebPUtilClearPic(canvas, gif_rect);
395 }
396}
397
398int WebPFrameCacheAddFrame(WebPFrameCache* const cache,
399 const WebPConfig* const config,
400 const WebPFrameRect* const orig_rect,
401 WebPPicture* const frame,
402 WebPMuxFrameInfo* const info) {
403 int ok = 0;
404 WebPFrameRect rect = *orig_rect;
405 WebPPicture sub_image; // View extracted from 'frame' with rectangle 'rect'.
406 WebPPicture* const prev_canvas = &cache->prev_canvas;
407 const size_t position = cache->count;
408 EncodedFrame* const encoded_frame = CacheGetFrame(cache, position);
409 assert(position < cache->size);
410
411 // Snap to even offsets (and adjust dimensions if needed).
412 rect.width += (rect.x_offset & 1);
413 rect.height += (rect.y_offset & 1);
414 rect.x_offset &= ~1;
415 rect.y_offset &= ~1;
416
417 if (!WebPPictureView(frame, rect.x_offset, rect.y_offset,
418 rect.width, rect.height, &sub_image)) {
419 return 0;
420 }
421 info->x_offset = rect.x_offset;
422 info->y_offset = rect.y_offset;
423
424 ++cache->count;
425
426 if (cache->is_first_frame || IsKeyFrame(frame, &rect, prev_canvas)) {
427 // Add this as a key frame.
428 if (!SetFrame(config, 1, NULL, NULL, NULL, info, &sub_image,
429 encoded_frame)) {
430 goto End;
431 }
432 cache->keyframe = position;
433 cache->flush_count = cache->count;
434 cache->count_since_key_frame = 0;
435 // Update prev_canvas by simply copying from 'curr'.
436 CopyPixels(frame, prev_canvas);
437 } else {
438 ++cache->count_since_key_frame;
439 if (cache->count_since_key_frame <= cache->kmin) {
440 // Add this as a frame rectangle.
441 if (!SetFrame(config, 0, prev_canvas, frame, &rect, info, &sub_image,
442 encoded_frame)) {
443 goto End;
444 }
445 cache->flush_count = cache->count;
446 // Update prev_canvas by blending 'curr' into it.
447 BlendPixels(frame, orig_rect, prev_canvas);
448 } else {
449 WebPPicture full_image;
450 WebPMuxFrameInfo full_image_info;
451 int frame_added;
452 int64_t curr_delta;
453
454 // Add frame rectangle to cache.
455 if (!SetFrame(config, 0, prev_canvas, frame, &rect, info, &sub_image,
456 encoded_frame)) {
457 goto End;
458 }
459
460 // Convert to a key frame.
461 CopyPixels(frame, &cache->curr_canvas);
462 ConvertToKeyFrame(prev_canvas, &rect, &cache->curr_canvas);
463 if (!WebPPictureView(&cache->curr_canvas, rect.x_offset, rect.y_offset,
464 rect.width, rect.height, &full_image)) {
465 goto End;
466 }
467 full_image_info = *info;
468 full_image_info.x_offset = rect.x_offset;
469 full_image_info.y_offset = rect.y_offset;
470
471 // Add key frame to cache, too.
472 frame_added = SetFrame(config, 1, NULL, NULL, NULL, &full_image_info,
473 &full_image, encoded_frame);
474 WebPPictureFree(&full_image);
475 if (!frame_added) goto End;
476
477 // Analyze size difference of the two variants.
478 curr_delta = KeyFramePenalty(encoded_frame);
479 if (curr_delta <= cache->best_delta) { // Pick this as keyframe.
480 cache->keyframe = position;
481 cache->best_delta = curr_delta;
482 cache->flush_count = cache->count - 1; // We can flush previous frames.
483 }
484 if (cache->count_since_key_frame == cache->kmax) {
485 cache->flush_count = cache->count;
486 cache->count_since_key_frame = 0;
487 }
488
489 // Update prev_canvas by simply copying from 'curr_canvas'.
490 CopyPixels(&cache->curr_canvas, prev_canvas);
491 }
492 }
493
494 DisposeFrame(info->dispose_method, orig_rect, frame, prev_canvas);
495
496 cache->is_first_frame = 0;
497 ok = 1;
498
499 End:
500 WebPPictureFree(&sub_image);
501 if (!ok) --cache->count; // We reset the count, as the frame addition failed.
502 return ok;
503}
504
505WebPMuxError WebPFrameCacheFlush(WebPFrameCache* const cache, int verbose,
506 WebPMux* const mux) {
507 while (cache->flush_count > 0) {
508 WebPMuxFrameInfo* info;
509 WebPMuxError err;
510 EncodedFrame* const curr = CacheGetFrame(cache, 0);
511 // Pick frame or full canvas.
512 if (cache->keyframe == 0) {
513 info = &curr->key_frame;
514 info->blend_method = WEBP_MUX_NO_BLEND;
515 cache->keyframe = KEYFRAME_NONE;
516 cache->best_delta = DELTA_INFINITY;
517 } else {
518 info = &curr->sub_frame;
519 info->blend_method = WEBP_MUX_BLEND;
520 }
521 // Add to mux.
522 err = WebPMuxPushFrame(mux, info, 1);
523 if (err != WEBP_MUX_OK) return err;
524 if (verbose) {
525 printf("Added frame. offset:%d,%d duration:%d dispose:%d blend:%d\n",
526 info->x_offset, info->y_offset, info->duration,
527 info->dispose_method, info->blend_method);
528 }
529 FrameRelease(curr);
530 ++cache->start;
531 --cache->flush_count;
532 --cache->count;
533 if (cache->keyframe != KEYFRAME_NONE) --cache->keyframe;
534 }
535
536 if (cache->count == 0) CacheReset(cache);
537 return WEBP_MUX_OK;
538}
539
540WebPMuxError WebPFrameCacheFlushAll(WebPFrameCache* const cache, int verbose,
541 WebPMux* const mux) {
542 cache->flush_count = cache->count; // Force flushing of all frames.
543 return WebPFrameCacheFlush(cache, verbose, mux);
544}
545
546//------------------------------------------------------------------------------