1// Copyright 2014 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// Near-lossless image preprocessing adjusts pixel values to help
11// compressibility with a guarantee of maximum deviation between original and
12// resulting pixel values.
13//
14// Author: Jyrki Alakuijala (jyrki@google.com)
15// Converted to C by Aleksander Kramarz (akramarz@google.com)
16
17#include <stdlib.h>
18
19#include "../dsp/lossless.h"
20#include "../utils/utils.h"
21#include "./vp8enci.h"
22
23#define MIN_DIM_FOR_NEAR_LOSSLESS 64
24#define MAX_LIMIT_BITS             5
25
26// Computes quantized pixel value and distance from original value.
27static void GetValAndDistance(int a, int initial, int bits,
28                              int* const val, int* const distance) {
29  const int mask = ~((1 << bits) - 1);
30  *val = (initial & mask) | (initial >> (8 - bits));
31  *distance = 2 * abs(a - *val);
32}
33
34// Clamps the value to range [0, 255].
35static int Clamp8b(int val) {
36  const int min_val = 0;
37  const int max_val = 0xff;
38  return (val < min_val) ? min_val : (val > max_val) ? max_val : val;
39}
40
41// Quantizes values {a, a+(1<<bits), a-(1<<bits)} and returns the nearest one.
42static int FindClosestDiscretized(int a, int bits) {
43  int best_val = a, i;
44  int min_distance = 256;
45
46  for (i = -1; i <= 1; ++i) {
47    int candidate, distance;
48    const int val = Clamp8b(a + i * (1 << bits));
49    GetValAndDistance(a, val, bits, &candidate, &distance);
50    if (i != 0) {
51      ++distance;
52    }
53    // Smallest distance but favor i == 0 over i == -1 and i == 1
54    // since that keeps the overall intensity more constant in the
55    // images.
56    if (distance < min_distance) {
57      min_distance = distance;
58      best_val = candidate;
59    }
60  }
61  return best_val;
62}
63
64// Applies FindClosestDiscretized to all channels of pixel.
65static uint32_t ClosestDiscretizedArgb(uint32_t a, int bits) {
66  return
67      (FindClosestDiscretized(a >> 24, bits) << 24) |
68      (FindClosestDiscretized((a >> 16) & 0xff, bits) << 16) |
69      (FindClosestDiscretized((a >> 8) & 0xff, bits) << 8) |
70      (FindClosestDiscretized(a & 0xff, bits));
71}
72
73// Checks if distance between corresponding channel values of pixels a and b
74// is within the given limit.
75static int IsNear(uint32_t a, uint32_t b, int limit) {
76  int k;
77  for (k = 0; k < 4; ++k) {
78    const int delta =
79        (int)((a >> (k * 8)) & 0xff) - (int)((b >> (k * 8)) & 0xff);
80    if (delta >= limit || delta <= -limit) {
81      return 0;
82    }
83  }
84  return 1;
85}
86
87static int IsSmooth(const uint32_t* const prev_row,
88                    const uint32_t* const curr_row,
89                    const uint32_t* const next_row,
90                    int ix, int limit) {
91  // Check that all pixels in 4-connected neighborhood are smooth.
92  return (IsNear(curr_row[ix], curr_row[ix - 1], limit) &&
93          IsNear(curr_row[ix], curr_row[ix + 1], limit) &&
94          IsNear(curr_row[ix], prev_row[ix], limit) &&
95          IsNear(curr_row[ix], next_row[ix], limit));
96}
97
98// Adjusts pixel values of image with given maximum error.
99static void NearLossless(int xsize, int ysize, uint32_t* argb,
100                         int limit_bits, uint32_t* copy_buffer) {
101  int x, y;
102  const int limit = 1 << limit_bits;
103  uint32_t* prev_row = copy_buffer;
104  uint32_t* curr_row = prev_row + xsize;
105  uint32_t* next_row = curr_row + xsize;
106  memcpy(copy_buffer, argb, xsize * 2 * sizeof(argb[0]));
107
108  for (y = 1; y < ysize - 1; ++y) {
109    uint32_t* const curr_argb_row = argb + y * xsize;
110    uint32_t* const next_argb_row = curr_argb_row + xsize;
111    memcpy(next_row, next_argb_row, xsize * sizeof(argb[0]));
112    for (x = 1; x < xsize - 1; ++x) {
113      if (!IsSmooth(prev_row, curr_row, next_row, x, limit)) {
114        curr_argb_row[x] = ClosestDiscretizedArgb(curr_row[x], limit_bits);
115      }
116    }
117    {
118      // Three-way swap.
119      uint32_t* const temp = prev_row;
120      prev_row = curr_row;
121      curr_row = next_row;
122      next_row = temp;
123    }
124  }
125}
126
127static int QualityToLimitBits(int quality) {
128  // quality mapping:
129  //  0..19 -> 5
130  //  0..39 -> 4
131  //  0..59 -> 3
132  //  0..79 -> 2
133  //  0..99 -> 1
134  //  100   -> 0
135  return MAX_LIMIT_BITS - quality / 20;
136}
137
138int VP8ApplyNearLossless(int xsize, int ysize, uint32_t* argb, int quality) {
139  int i;
140  uint32_t* const copy_buffer =
141      (uint32_t*)WebPSafeMalloc(xsize * 3, sizeof(*copy_buffer));
142  const int limit_bits = QualityToLimitBits(quality);
143  assert(argb != NULL);
144  assert(limit_bits >= 0);
145  assert(limit_bits <= MAX_LIMIT_BITS);
146  if (copy_buffer == NULL) {
147    return 0;
148  }
149  // For small icon images, don't attempt to apply near-lossless compression.
150  if (xsize < MIN_DIM_FOR_NEAR_LOSSLESS && ysize < MIN_DIM_FOR_NEAR_LOSSLESS) {
151    WebPSafeFree(copy_buffer);
152    return 1;
153  }
154
155  for (i = limit_bits; i != 0; --i) {
156    NearLossless(xsize, ysize, argb, i, copy_buffer);
157  }
158  WebPSafeFree(copy_buffer);
159  return 1;
160}
161