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