1// Copyright 2011 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// VP8Iterator: block iterator
11//
12// Author: Skal (pascal.massimino@gmail.com)
13
14#include <string.h>
15
16#include "./vp8enci.h"
17
18//------------------------------------------------------------------------------
19// VP8Iterator
20//------------------------------------------------------------------------------
21
22static void InitLeft(VP8EncIterator* const it) {
23  it->y_left_[-1] = it->u_left_[-1] = it->v_left_[-1] =
24      (it->y_ > 0) ? 129 : 127;
25  memset(it->y_left_, 129, 16);
26  memset(it->u_left_, 129, 8);
27  memset(it->v_left_, 129, 8);
28  it->left_nz_[8] = 0;
29}
30
31static void InitTop(VP8EncIterator* const it) {
32  const VP8Encoder* const enc = it->enc_;
33  const size_t top_size = enc->mb_w_ * 16;
34  memset(enc->y_top_, 127, 2 * top_size);
35  memset(enc->nz_, 0, enc->mb_w_ * sizeof(*enc->nz_));
36}
37
38void VP8IteratorSetRow(VP8EncIterator* const it, int y) {
39  VP8Encoder* const enc = it->enc_;
40  it->x_ = 0;
41  it->y_ = y;
42  it->bw_ = &enc->parts_[y & (enc->num_parts_ - 1)];
43  it->preds_ = enc->preds_ + y * 4 * enc->preds_w_;
44  it->nz_ = enc->nz_;
45  it->mb_ = enc->mb_info_ + y * enc->mb_w_;
46  it->y_top_ = enc->y_top_;
47  it->uv_top_ = enc->uv_top_;
48  InitLeft(it);
49}
50
51void VP8IteratorReset(VP8EncIterator* const it) {
52  VP8Encoder* const enc = it->enc_;
53  VP8IteratorSetRow(it, 0);
54  VP8IteratorSetCountDown(it, enc->mb_w_ * enc->mb_h_);  // default
55  InitTop(it);
56  InitLeft(it);
57  memset(it->bit_count_, 0, sizeof(it->bit_count_));
58  it->do_trellis_ = 0;
59}
60
61void VP8IteratorSetCountDown(VP8EncIterator* const it, int count_down) {
62  it->count_down_ = it->count_down0_ = count_down;
63}
64
65int VP8IteratorIsDone(const VP8EncIterator* const it) {
66  return (it->count_down_ <= 0);
67}
68
69void VP8IteratorInit(VP8Encoder* const enc, VP8EncIterator* const it) {
70  it->enc_ = enc;
71  it->y_stride_  = enc->pic_->y_stride;
72  it->uv_stride_ = enc->pic_->uv_stride;
73  it->yuv_in_   = (uint8_t*)WEBP_ALIGN(it->yuv_mem_);
74  it->yuv_out_  = it->yuv_in_ + YUV_SIZE_ENC;
75  it->yuv_out2_ = it->yuv_out_ + YUV_SIZE_ENC;
76  it->yuv_p_    = it->yuv_out2_ + YUV_SIZE_ENC;
77  it->lf_stats_ = enc->lf_stats_;
78  it->percent0_ = enc->percent_;
79  it->y_left_ = (uint8_t*)WEBP_ALIGN(it->yuv_left_mem_ + 1);
80  it->u_left_ = it->y_left_ + 16 + 16;
81  it->v_left_ = it->u_left_ + 16;
82  VP8IteratorReset(it);
83}
84
85int VP8IteratorProgress(const VP8EncIterator* const it, int delta) {
86  VP8Encoder* const enc = it->enc_;
87  if (delta && enc->pic_->progress_hook != NULL) {
88    const int done = it->count_down0_ - it->count_down_;
89    const int percent = (it->count_down0_ <= 0)
90                      ? it->percent0_
91                      : it->percent0_ + delta * done / it->count_down0_;
92    return WebPReportProgress(enc->pic_, percent, &enc->percent_);
93  }
94  return 1;
95}
96
97//------------------------------------------------------------------------------
98// Import the source samples into the cache. Takes care of replicating
99// boundary pixels if necessary.
100
101static WEBP_INLINE int MinSize(int a, int b) { return (a < b) ? a : b; }
102
103static void ImportBlock(const uint8_t* src, int src_stride,
104                        uint8_t* dst, int w, int h, int size) {
105  int i;
106  for (i = 0; i < h; ++i) {
107    memcpy(dst, src, w);
108    if (w < size) {
109      memset(dst + w, dst[w - 1], size - w);
110    }
111    dst += BPS;
112    src += src_stride;
113  }
114  for (i = h; i < size; ++i) {
115    memcpy(dst, dst - BPS, size);
116    dst += BPS;
117  }
118}
119
120static void ImportLine(const uint8_t* src, int src_stride,
121                       uint8_t* dst, int len, int total_len) {
122  int i;
123  for (i = 0; i < len; ++i, src += src_stride) dst[i] = *src;
124  for (; i < total_len; ++i) dst[i] = dst[len - 1];
125}
126
127void VP8IteratorImport(VP8EncIterator* const it, uint8_t* tmp_32) {
128  const VP8Encoder* const enc = it->enc_;
129  const int x = it->x_, y = it->y_;
130  const WebPPicture* const pic = enc->pic_;
131  const uint8_t* const ysrc = pic->y + (y * pic->y_stride  + x) * 16;
132  const uint8_t* const usrc = pic->u + (y * pic->uv_stride + x) * 8;
133  const uint8_t* const vsrc = pic->v + (y * pic->uv_stride + x) * 8;
134  const int w = MinSize(pic->width - x * 16, 16);
135  const int h = MinSize(pic->height - y * 16, 16);
136  const int uv_w = (w + 1) >> 1;
137  const int uv_h = (h + 1) >> 1;
138
139  ImportBlock(ysrc, pic->y_stride,  it->yuv_in_ + Y_OFF_ENC, w, h, 16);
140  ImportBlock(usrc, pic->uv_stride, it->yuv_in_ + U_OFF_ENC, uv_w, uv_h, 8);
141  ImportBlock(vsrc, pic->uv_stride, it->yuv_in_ + V_OFF_ENC, uv_w, uv_h, 8);
142
143  if (tmp_32 == NULL) return;
144
145  // Import source (uncompressed) samples into boundary.
146  if (x == 0) {
147    InitLeft(it);
148  } else {
149    if (y == 0) {
150      it->y_left_[-1] = it->u_left_[-1] = it->v_left_[-1] = 127;
151    } else {
152      it->y_left_[-1] = ysrc[- 1 - pic->y_stride];
153      it->u_left_[-1] = usrc[- 1 - pic->uv_stride];
154      it->v_left_[-1] = vsrc[- 1 - pic->uv_stride];
155    }
156    ImportLine(ysrc - 1, pic->y_stride,  it->y_left_, h,   16);
157    ImportLine(usrc - 1, pic->uv_stride, it->u_left_, uv_h, 8);
158    ImportLine(vsrc - 1, pic->uv_stride, it->v_left_, uv_h, 8);
159  }
160
161  it->y_top_  = tmp_32 + 0;
162  it->uv_top_ = tmp_32 + 16;
163  if (y == 0) {
164    memset(tmp_32, 127, 32 * sizeof(*tmp_32));
165  } else {
166    ImportLine(ysrc - pic->y_stride,  1, tmp_32,          w,   16);
167    ImportLine(usrc - pic->uv_stride, 1, tmp_32 + 16,     uv_w, 8);
168    ImportLine(vsrc - pic->uv_stride, 1, tmp_32 + 16 + 8, uv_w, 8);
169  }
170}
171
172//------------------------------------------------------------------------------
173// Copy back the compressed samples into user space if requested.
174
175static void ExportBlock(const uint8_t* src, uint8_t* dst, int dst_stride,
176                        int w, int h) {
177  while (h-- > 0) {
178    memcpy(dst, src, w);
179    dst += dst_stride;
180    src += BPS;
181  }
182}
183
184void VP8IteratorExport(const VP8EncIterator* const it) {
185  const VP8Encoder* const enc = it->enc_;
186  if (enc->config_->show_compressed) {
187    const int x = it->x_, y = it->y_;
188    const uint8_t* const ysrc = it->yuv_out_ + Y_OFF_ENC;
189    const uint8_t* const usrc = it->yuv_out_ + U_OFF_ENC;
190    const uint8_t* const vsrc = it->yuv_out_ + V_OFF_ENC;
191    const WebPPicture* const pic = enc->pic_;
192    uint8_t* const ydst = pic->y + (y * pic->y_stride + x) * 16;
193    uint8_t* const udst = pic->u + (y * pic->uv_stride + x) * 8;
194    uint8_t* const vdst = pic->v + (y * pic->uv_stride + x) * 8;
195    int w = (pic->width - x * 16);
196    int h = (pic->height - y * 16);
197
198    if (w > 16) w = 16;
199    if (h > 16) h = 16;
200
201    // Luma plane
202    ExportBlock(ysrc, ydst, pic->y_stride, w, h);
203
204    {   // U/V planes
205      const int uv_w = (w + 1) >> 1;
206      const int uv_h = (h + 1) >> 1;
207      ExportBlock(usrc, udst, pic->uv_stride, uv_w, uv_h);
208      ExportBlock(vsrc, vdst, pic->uv_stride, uv_w, uv_h);
209    }
210  }
211}
212
213//------------------------------------------------------------------------------
214// Non-zero contexts setup/teardown
215
216// Nz bits:
217//  0  1  2  3  Y
218//  4  5  6  7
219//  8  9 10 11
220// 12 13 14 15
221// 16 17        U
222// 18 19
223// 20 21        V
224// 22 23
225// 24           DC-intra16
226
227// Convert packed context to byte array
228#define BIT(nz, n) (!!((nz) & (1 << (n))))
229
230void VP8IteratorNzToBytes(VP8EncIterator* const it) {
231  const int tnz = it->nz_[0], lnz = it->nz_[-1];
232  int* const top_nz = it->top_nz_;
233  int* const left_nz = it->left_nz_;
234
235  // Top-Y
236  top_nz[0] = BIT(tnz, 12);
237  top_nz[1] = BIT(tnz, 13);
238  top_nz[2] = BIT(tnz, 14);
239  top_nz[3] = BIT(tnz, 15);
240  // Top-U
241  top_nz[4] = BIT(tnz, 18);
242  top_nz[5] = BIT(tnz, 19);
243  // Top-V
244  top_nz[6] = BIT(tnz, 22);
245  top_nz[7] = BIT(tnz, 23);
246  // DC
247  top_nz[8] = BIT(tnz, 24);
248
249  // left-Y
250  left_nz[0] = BIT(lnz,  3);
251  left_nz[1] = BIT(lnz,  7);
252  left_nz[2] = BIT(lnz, 11);
253  left_nz[3] = BIT(lnz, 15);
254  // left-U
255  left_nz[4] = BIT(lnz, 17);
256  left_nz[5] = BIT(lnz, 19);
257  // left-V
258  left_nz[6] = BIT(lnz, 21);
259  left_nz[7] = BIT(lnz, 23);
260  // left-DC is special, iterated separately
261}
262
263void VP8IteratorBytesToNz(VP8EncIterator* const it) {
264  uint32_t nz = 0;
265  const int* const top_nz = it->top_nz_;
266  const int* const left_nz = it->left_nz_;
267  // top
268  nz |= (top_nz[0] << 12) | (top_nz[1] << 13);
269  nz |= (top_nz[2] << 14) | (top_nz[3] << 15);
270  nz |= (top_nz[4] << 18) | (top_nz[5] << 19);
271  nz |= (top_nz[6] << 22) | (top_nz[7] << 23);
272  nz |= (top_nz[8] << 24);  // we propagate the _top_ bit, esp. for intra4
273  // left
274  nz |= (left_nz[0] << 3) | (left_nz[1] << 7);
275  nz |= (left_nz[2] << 11);
276  nz |= (left_nz[4] << 17) | (left_nz[6] << 21);
277
278  *it->nz_ = nz;
279}
280
281#undef BIT
282
283//------------------------------------------------------------------------------
284// Advance to the next position, doing the bookkeeping.
285
286void VP8IteratorSaveBoundary(VP8EncIterator* const it) {
287  VP8Encoder* const enc = it->enc_;
288  const int x = it->x_, y = it->y_;
289  const uint8_t* const ysrc = it->yuv_out_ + Y_OFF_ENC;
290  const uint8_t* const uvsrc = it->yuv_out_ + U_OFF_ENC;
291  if (x < enc->mb_w_ - 1) {   // left
292    int i;
293    for (i = 0; i < 16; ++i) {
294      it->y_left_[i] = ysrc[15 + i * BPS];
295    }
296    for (i = 0; i < 8; ++i) {
297      it->u_left_[i] = uvsrc[7 + i * BPS];
298      it->v_left_[i] = uvsrc[15 + i * BPS];
299    }
300    // top-left (before 'top'!)
301    it->y_left_[-1] = it->y_top_[15];
302    it->u_left_[-1] = it->uv_top_[0 + 7];
303    it->v_left_[-1] = it->uv_top_[8 + 7];
304  }
305  if (y < enc->mb_h_ - 1) {  // top
306    memcpy(it->y_top_, ysrc + 15 * BPS, 16);
307    memcpy(it->uv_top_, uvsrc + 7 * BPS, 8 + 8);
308  }
309}
310
311int VP8IteratorNext(VP8EncIterator* const it) {
312  it->preds_ += 4;
313  it->mb_ += 1;
314  it->nz_ += 1;
315  it->y_top_ += 16;
316  it->uv_top_ += 16;
317  it->x_ += 1;
318  if (it->x_ == it->enc_->mb_w_) {
319    VP8IteratorSetRow(it, ++it->y_);
320  }
321  return (0 < --it->count_down_);
322}
323
324//------------------------------------------------------------------------------
325// Helper function to set mode properties
326
327void VP8SetIntra16Mode(const VP8EncIterator* const it, int mode) {
328  uint8_t* preds = it->preds_;
329  int y;
330  for (y = 0; y < 4; ++y) {
331    memset(preds, mode, 4);
332    preds += it->enc_->preds_w_;
333  }
334  it->mb_->type_ = 1;
335}
336
337void VP8SetIntra4Mode(const VP8EncIterator* const it, const uint8_t* modes) {
338  uint8_t* preds = it->preds_;
339  int y;
340  for (y = 4; y > 0; --y) {
341    memcpy(preds, modes, 4 * sizeof(*modes));
342    preds += it->enc_->preds_w_;
343    modes += 4;
344  }
345  it->mb_->type_ = 0;
346}
347
348void VP8SetIntraUVMode(const VP8EncIterator* const it, int mode) {
349  it->mb_->uv_mode_ = mode;
350}
351
352void VP8SetSkip(const VP8EncIterator* const it, int skip) {
353  it->mb_->skip_ = skip;
354}
355
356void VP8SetSegment(const VP8EncIterator* const it, int segment) {
357  it->mb_->segment_ = segment;
358}
359
360//------------------------------------------------------------------------------
361// Intra4x4 sub-blocks iteration
362//
363//  We store and update the boundary samples into an array of 37 pixels. They
364//  are updated as we iterate and reconstructs each intra4x4 blocks in turn.
365//  The position of the samples has the following snake pattern:
366//
367// 16|17 18 19 20|21 22 23 24|25 26 27 28|29 30 31 32|33 34 35 36  <- Top-right
368// --+-----------+-----------+-----------+-----------+
369// 15|         19|         23|         27|         31|
370// 14|         18|         22|         26|         30|
371// 13|         17|         21|         25|         29|
372// 12|13 14 15 16|17 18 19 20|21 22 23 24|25 26 27 28|
373// --+-----------+-----------+-----------+-----------+
374// 11|         15|         19|         23|         27|
375// 10|         14|         18|         22|         26|
376//  9|         13|         17|         21|         25|
377//  8| 9 10 11 12|13 14 15 16|17 18 19 20|21 22 23 24|
378// --+-----------+-----------+-----------+-----------+
379//  7|         11|         15|         19|         23|
380//  6|         10|         14|         18|         22|
381//  5|          9|         13|         17|         21|
382//  4| 5  6  7  8| 9 10 11 12|13 14 15 16|17 18 19 20|
383// --+-----------+-----------+-----------+-----------+
384//  3|          7|         11|         15|         19|
385//  2|          6|         10|         14|         18|
386//  1|          5|          9|         13|         17|
387//  0| 1  2  3  4| 5  6  7  8| 9 10 11 12|13 14 15 16|
388// --+-----------+-----------+-----------+-----------+
389
390// Array to record the position of the top sample to pass to the prediction
391// functions in dsp.c.
392static const uint8_t VP8TopLeftI4[16] = {
393  17, 21, 25, 29,
394  13, 17, 21, 25,
395  9,  13, 17, 21,
396  5,   9, 13, 17
397};
398
399void VP8IteratorStartI4(VP8EncIterator* const it) {
400  const VP8Encoder* const enc = it->enc_;
401  int i;
402
403  it->i4_ = 0;    // first 4x4 sub-block
404  it->i4_top_ = it->i4_boundary_ + VP8TopLeftI4[0];
405
406  // Import the boundary samples
407  for (i = 0; i < 17; ++i) {    // left
408    it->i4_boundary_[i] = it->y_left_[15 - i];
409  }
410  for (i = 0; i < 16; ++i) {    // top
411    it->i4_boundary_[17 + i] = it->y_top_[i];
412  }
413  // top-right samples have a special case on the far right of the picture
414  if (it->x_ < enc->mb_w_ - 1) {
415    for (i = 16; i < 16 + 4; ++i) {
416      it->i4_boundary_[17 + i] = it->y_top_[i];
417    }
418  } else {    // else, replicate the last valid pixel four times
419    for (i = 16; i < 16 + 4; ++i) {
420      it->i4_boundary_[17 + i] = it->i4_boundary_[17 + 15];
421    }
422  }
423  VP8IteratorNzToBytes(it);  // import the non-zero context
424}
425
426int VP8IteratorRotateI4(VP8EncIterator* const it,
427                        const uint8_t* const yuv_out) {
428  const uint8_t* const blk = yuv_out + VP8Scan[it->i4_];
429  uint8_t* const top = it->i4_top_;
430  int i;
431
432  // Update the cache with 7 fresh samples
433  for (i = 0; i <= 3; ++i) {
434    top[-4 + i] = blk[i + 3 * BPS];   // store future top samples
435  }
436  if ((it->i4_ & 3) != 3) {  // if not on the right sub-blocks #3, #7, #11, #15
437    for (i = 0; i <= 2; ++i) {        // store future left samples
438      top[i] = blk[3 + (2 - i) * BPS];
439    }
440  } else {  // else replicate top-right samples, as says the specs.
441    for (i = 0; i <= 3; ++i) {
442      top[i] = top[i + 4];
443    }
444  }
445  // move pointers to next sub-block
446  ++it->i4_;
447  if (it->i4_ == 16) {    // we're done
448    return 0;
449  }
450
451  it->i4_top_ = it->i4_boundary_ + VP8TopLeftI4[it->i4_];
452  return 1;
453}
454
455//------------------------------------------------------------------------------
456
457