license.bot | f003cfe | 2008-08-24 09:55:55 +0900 | [diff] [blame^] | 1 | // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
initial.commit | 3f4a732 | 2008-07-27 06:49:38 +0900 | [diff] [blame] | 4 | |
| 5 | #include <algorithm> |
| 6 | |
| 7 | #include "base/basictypes.h" |
| 8 | #include "base/gfx/convolver.h" |
| 9 | #include "base/logging.h" |
| 10 | |
| 11 | namespace gfx { |
| 12 | |
| 13 | namespace { |
| 14 | |
| 15 | // Converts the argument to an 8-bit unsigned value by clamping to the range |
| 16 | // 0-255. |
| 17 | inline uint8 ClampTo8(int32 a) { |
| 18 | if (static_cast<uint32>(a) < 256) |
| 19 | return a; // Avoid the extra check in the common case. |
| 20 | if (a < 0) |
| 21 | return 0; |
| 22 | return 255; |
| 23 | } |
| 24 | |
| 25 | // Stores a list of rows in a circular buffer. The usage is you write into it |
| 26 | // by calling AdvanceRow. It will keep track of which row in the buffer it |
| 27 | // should use next, and the total number of rows added. |
| 28 | class CircularRowBuffer { |
| 29 | public: |
| 30 | // The number of pixels in each row is given in |source_row_pixel_width|. |
| 31 | // The maximum number of rows needed in the buffer is |max_y_filter_size| |
| 32 | // (we only need to store enough rows for the biggest filter). |
| 33 | // |
| 34 | // We use the |first_input_row| to compute the coordinates of all of the |
| 35 | // following rows returned by Advance(). |
| 36 | CircularRowBuffer(int dest_row_pixel_width, int max_y_filter_size, |
| 37 | int first_input_row) |
| 38 | : row_byte_width_(dest_row_pixel_width * 4), |
| 39 | num_rows_(max_y_filter_size), |
| 40 | next_row_(0), |
| 41 | next_row_coordinate_(first_input_row) { |
| 42 | buffer_.resize(row_byte_width_ * max_y_filter_size); |
| 43 | row_addresses_.resize(num_rows_); |
| 44 | } |
| 45 | |
| 46 | // Moves to the next row in the buffer, returning a pointer to the beginning |
| 47 | // of it. |
| 48 | uint8* AdvanceRow() { |
| 49 | uint8* row = &buffer_[next_row_ * row_byte_width_]; |
| 50 | next_row_coordinate_++; |
| 51 | |
| 52 | // Set the pointer to the next row to use, wrapping around if necessary. |
| 53 | next_row_++; |
| 54 | if (next_row_ == num_rows_) |
| 55 | next_row_ = 0; |
| 56 | return row; |
| 57 | } |
| 58 | |
| 59 | // Returns a pointer to an "unrolled" array of rows. These rows will start |
| 60 | // at the y coordinate placed into |*first_row_index| and will continue in |
| 61 | // order for the maximum number of rows in this circular buffer. |
| 62 | // |
| 63 | // The |first_row_index_| may be negative. This means the circular buffer |
| 64 | // starts before the top of the image (it hasn't been filled yet). |
| 65 | uint8* const* GetRowAddresses(int* first_row_index) { |
| 66 | // Example for a 4-element circular buffer holding coords 6-9. |
| 67 | // Row 0 Coord 8 |
| 68 | // Row 1 Coord 9 |
| 69 | // Row 2 Coord 6 <- next_row_ = 2, next_row_coordinate_ = 10. |
| 70 | // Row 3 Coord 7 |
| 71 | // |
| 72 | // The "next" row is also the first (lowest) coordinate. This computation |
| 73 | // may yield a negative value, but that's OK, the math will work out |
| 74 | // since the user of this buffer will compute the offset relative |
| 75 | // to the first_row_index and the negative rows will never be used. |
| 76 | *first_row_index = next_row_coordinate_ - num_rows_; |
| 77 | |
| 78 | int cur_row = next_row_; |
| 79 | for (int i = 0; i < num_rows_; i++) { |
| 80 | row_addresses_[i] = &buffer_[cur_row * row_byte_width_]; |
| 81 | |
ericroman@google.com | dbff4f5 | 2008-08-19 01:00:38 +0900 | [diff] [blame] | 82 | // Advance to the next row, wrapping if necessary. |
initial.commit | 3f4a732 | 2008-07-27 06:49:38 +0900 | [diff] [blame] | 83 | cur_row++; |
| 84 | if (cur_row == num_rows_) |
| 85 | cur_row = 0; |
| 86 | } |
| 87 | return &row_addresses_[0]; |
| 88 | } |
| 89 | |
| 90 | private: |
| 91 | // The buffer storing the rows. They are packed, each one row_byte_width_. |
| 92 | std::vector<uint8> buffer_; |
| 93 | |
| 94 | // Number of bytes per row in the |buffer_|. |
| 95 | int row_byte_width_; |
| 96 | |
| 97 | // The number of rows available in the buffer. |
| 98 | int num_rows_; |
| 99 | |
| 100 | // The next row index we should write into. This wraps around as the |
| 101 | // circular buffer is used. |
| 102 | int next_row_; |
| 103 | |
| 104 | // The y coordinate of the |next_row_|. This is incremented each time a |
| 105 | // new row is appended and does not wrap. |
| 106 | int next_row_coordinate_; |
| 107 | |
| 108 | // Buffer used by GetRowAddresses(). |
| 109 | std::vector<uint8*> row_addresses_; |
| 110 | }; |
| 111 | |
| 112 | // Convolves horizontally along a single row. The row data is given in |
| 113 | // |src_data| and continues for the num_values() of the filter. |
| 114 | template<bool has_alpha> |
| 115 | void ConvolveHorizontally(const uint8* src_data, |
| 116 | const ConvolusionFilter1D& filter, |
| 117 | unsigned char* out_row) { |
| 118 | // Loop over each pixel on this row in the output image. |
| 119 | int num_values = filter.num_values(); |
| 120 | for (int out_x = 0; out_x < num_values; out_x++) { |
| 121 | // Get the filter that determines the current output pixel. |
| 122 | int filter_offset, filter_length; |
| 123 | const int16* filter_values = |
| 124 | filter.FilterForValue(out_x, &filter_offset, &filter_length); |
| 125 | |
| 126 | // Compute the first pixel in this row that the filter affects. It will |
| 127 | // touch |filter_length| pixels (4 bytes each) after this. |
| 128 | const uint8* row_to_filter = &src_data[filter_offset * 4]; |
| 129 | |
| 130 | // Apply the filter to the row to get the destination pixel in |accum|. |
| 131 | int32 accum[4] = {0}; |
| 132 | for (int filter_x = 0; filter_x < filter_length; filter_x++) { |
| 133 | int16 cur_filter = filter_values[filter_x]; |
| 134 | accum[0] += cur_filter * row_to_filter[filter_x * 4 + 0]; |
| 135 | accum[1] += cur_filter * row_to_filter[filter_x * 4 + 1]; |
| 136 | accum[2] += cur_filter * row_to_filter[filter_x * 4 + 2]; |
| 137 | if (has_alpha) |
| 138 | accum[3] += cur_filter * row_to_filter[filter_x * 4 + 3]; |
| 139 | } |
| 140 | |
| 141 | // Bring this value back in range. All of the filter scaling factors |
| 142 | // are in fixed point with kShiftBits bits of fractional part. |
| 143 | accum[0] >>= ConvolusionFilter1D::kShiftBits; |
| 144 | accum[1] >>= ConvolusionFilter1D::kShiftBits; |
| 145 | accum[2] >>= ConvolusionFilter1D::kShiftBits; |
| 146 | if (has_alpha) |
| 147 | accum[3] >>= ConvolusionFilter1D::kShiftBits; |
| 148 | |
| 149 | // Store the new pixel. |
| 150 | out_row[out_x * 4 + 0] = ClampTo8(accum[0]); |
| 151 | out_row[out_x * 4 + 1] = ClampTo8(accum[1]); |
| 152 | out_row[out_x * 4 + 2] = ClampTo8(accum[2]); |
| 153 | if (has_alpha) |
| 154 | out_row[out_x * 4 + 3] = ClampTo8(accum[3]); |
| 155 | } |
| 156 | } |
| 157 | |
| 158 | // Does vertical convolusion to produce one output row. The filter values and |
| 159 | // length are given in the first two parameters. These are applied to each |
| 160 | // of the rows pointed to in the |source_data_rows| array, with each row |
| 161 | // being |pixel_width| wide. |
| 162 | // |
| 163 | // The output must have room for |pixel_width * 4| bytes. |
| 164 | template<bool has_alpha> |
| 165 | void ConvolveVertically(const int16* filter_values, |
| 166 | int filter_length, |
| 167 | uint8* const* source_data_rows, |
| 168 | int pixel_width, |
| 169 | uint8* out_row) { |
| 170 | // We go through each column in the output and do a vertical convolusion, |
| 171 | // generating one output pixel each time. |
| 172 | for (int out_x = 0; out_x < pixel_width; out_x++) { |
| 173 | // Compute the number of bytes over in each row that the current column |
| 174 | // we're convolving starts at. The pixel will cover the next 4 bytes. |
| 175 | int byte_offset = out_x * 4; |
| 176 | |
| 177 | // Apply the filter to one column of pixels. |
| 178 | int32 accum[4] = {0}; |
| 179 | for (int filter_y = 0; filter_y < filter_length; filter_y++) { |
| 180 | int16 cur_filter = filter_values[filter_y]; |
| 181 | accum[0] += cur_filter * source_data_rows[filter_y][byte_offset + 0]; |
| 182 | accum[1] += cur_filter * source_data_rows[filter_y][byte_offset + 1]; |
| 183 | accum[2] += cur_filter * source_data_rows[filter_y][byte_offset + 2]; |
| 184 | if (has_alpha) |
| 185 | accum[3] += cur_filter * source_data_rows[filter_y][byte_offset + 3]; |
| 186 | } |
| 187 | |
| 188 | // Bring this value back in range. All of the filter scaling factors |
| 189 | // are in fixed point with kShiftBits bits of precision. |
| 190 | accum[0] >>= ConvolusionFilter1D::kShiftBits; |
| 191 | accum[1] >>= ConvolusionFilter1D::kShiftBits; |
| 192 | accum[2] >>= ConvolusionFilter1D::kShiftBits; |
| 193 | if (has_alpha) |
| 194 | accum[3] >>= ConvolusionFilter1D::kShiftBits; |
| 195 | |
| 196 | // Store the new pixel. |
| 197 | out_row[byte_offset + 0] = ClampTo8(accum[0]); |
| 198 | out_row[byte_offset + 1] = ClampTo8(accum[1]); |
| 199 | out_row[byte_offset + 2] = ClampTo8(accum[2]); |
| 200 | if (has_alpha) { |
| 201 | uint8 alpha = ClampTo8(accum[3]); |
| 202 | |
| 203 | // Make sure the alpha channel doesn't come out larger than any of the |
| 204 | // color channels. We use premultipled alpha channels, so this should |
| 205 | // never happen, but rounding errors will cause this from time to time. |
| 206 | // These "impossible" colors will cause overflows (and hence random pixel |
| 207 | // values) when the resulting bitmap is drawn to the screen. |
| 208 | // |
| 209 | // We only need to do this when generating the final output row (here). |
| 210 | int max_color_channel = std::max(out_row[byte_offset + 0], |
| 211 | std::max(out_row[byte_offset + 1], out_row[byte_offset + 2])); |
| 212 | if (alpha < max_color_channel) |
| 213 | out_row[byte_offset + 3] = max_color_channel; |
| 214 | else |
| 215 | out_row[byte_offset + 3] = alpha; |
| 216 | } else { |
ericroman@google.com | dbff4f5 | 2008-08-19 01:00:38 +0900 | [diff] [blame] | 217 | // No alpha channel, the image is opaque. |
initial.commit | 3f4a732 | 2008-07-27 06:49:38 +0900 | [diff] [blame] | 218 | out_row[byte_offset + 3] = 0xff; |
| 219 | } |
| 220 | } |
| 221 | } |
| 222 | |
| 223 | } // namespace |
| 224 | |
| 225 | // ConvolusionFilter1D --------------------------------------------------------- |
| 226 | |
| 227 | void ConvolusionFilter1D::AddFilter(int filter_offset, |
| 228 | const float* filter_values, |
| 229 | int filter_length) { |
| 230 | FilterInstance instance; |
| 231 | instance.data_location = static_cast<int>(filter_values_.size()); |
| 232 | instance.offset = filter_offset; |
| 233 | instance.length = filter_length; |
| 234 | filters_.push_back(instance); |
| 235 | |
| 236 | DCHECK(filter_length > 0); |
| 237 | for (int i = 0; i < filter_length; i++) |
| 238 | filter_values_.push_back(FloatToFixed(filter_values[i])); |
| 239 | |
| 240 | max_filter_ = std::max(max_filter_, filter_length); |
| 241 | } |
| 242 | |
| 243 | void ConvolusionFilter1D::AddFilter(int filter_offset, |
| 244 | const int16* filter_values, |
| 245 | int filter_length) { |
| 246 | FilterInstance instance; |
| 247 | instance.data_location = static_cast<int>(filter_values_.size()); |
| 248 | instance.offset = filter_offset; |
| 249 | instance.length = filter_length; |
| 250 | filters_.push_back(instance); |
| 251 | |
| 252 | DCHECK(filter_length > 0); |
| 253 | for (int i = 0; i < filter_length; i++) |
| 254 | filter_values_.push_back(filter_values[i]); |
| 255 | |
| 256 | max_filter_ = std::max(max_filter_, filter_length); |
| 257 | } |
| 258 | |
| 259 | // BGRAConvolve2D ------------------------------------------------------------- |
| 260 | |
| 261 | void BGRAConvolve2D(const uint8* source_data, |
| 262 | int source_byte_row_stride, |
| 263 | bool source_has_alpha, |
| 264 | const ConvolusionFilter1D& filter_x, |
| 265 | const ConvolusionFilter1D& filter_y, |
| 266 | uint8* output) { |
| 267 | int max_y_filter_size = filter_y.max_filter(); |
| 268 | |
| 269 | // The next row in the input that we will generate a horizontally |
| 270 | // convolved row for. If the filter doesn't start at the beginning of the |
| 271 | // image (this is the case when we are only resizing a subset), then we |
| 272 | // don't want to generate any output rows before that. Compute the starting |
| 273 | // row for convolusion as the first pixel for the first vertical filter. |
| 274 | int filter_offset, filter_length; |
| 275 | const int16* filter_values = |
| 276 | filter_y.FilterForValue(0, &filter_offset, &filter_length); |
| 277 | int next_x_row = filter_offset; |
| 278 | |
| 279 | // We loop over each row in the input doing a horizontal convolusion. This |
| 280 | // will result in a horizontally convolved image. We write the results into |
| 281 | // a circular buffer of convolved rows and do vertical convolusion as rows |
| 282 | // are available. This prevents us from having to store the entire |
| 283 | // intermediate image and helps cache coherency. |
| 284 | CircularRowBuffer row_buffer(filter_x.num_values(), max_y_filter_size, |
| 285 | filter_offset); |
| 286 | |
| 287 | // Loop over every possible output row, processing just enough horizontal |
| 288 | // convolusions to run each subsequent vertical convolusion. |
| 289 | int output_row_byte_width = filter_x.num_values() * 4; |
| 290 | int num_output_rows = filter_y.num_values(); |
| 291 | for (int out_y = 0; out_y < num_output_rows; out_y++) { |
| 292 | filter_values = filter_y.FilterForValue(out_y, |
| 293 | &filter_offset, &filter_length); |
| 294 | |
| 295 | // Generate output rows until we have enough to run the current filter. |
| 296 | while (next_x_row < filter_offset + filter_length) { |
| 297 | if (source_has_alpha) { |
| 298 | ConvolveHorizontally<true>( |
| 299 | &source_data[next_x_row * source_byte_row_stride], |
| 300 | filter_x, row_buffer.AdvanceRow()); |
| 301 | } else { |
| 302 | ConvolveHorizontally<false>( |
| 303 | &source_data[next_x_row * source_byte_row_stride], |
| 304 | filter_x, row_buffer.AdvanceRow()); |
| 305 | } |
| 306 | next_x_row++; |
| 307 | } |
| 308 | |
| 309 | // Compute where in the output image this row of final data will go. |
| 310 | uint8* cur_output_row = &output[out_y * output_row_byte_width]; |
| 311 | |
| 312 | // Get the list of rows that the circular buffer has, in order. |
| 313 | int first_row_in_circular_buffer; |
| 314 | uint8* const* rows_to_convolve = |
| 315 | row_buffer.GetRowAddresses(&first_row_in_circular_buffer); |
| 316 | |
| 317 | // Now compute the start of the subset of those rows that the filter |
| 318 | // needs. |
| 319 | uint8* const* first_row_for_filter = |
| 320 | &rows_to_convolve[filter_offset - first_row_in_circular_buffer]; |
| 321 | |
| 322 | if (source_has_alpha) { |
| 323 | ConvolveVertically<true>(filter_values, filter_length, |
| 324 | first_row_for_filter, |
| 325 | filter_x.num_values(), cur_output_row); |
| 326 | } else { |
| 327 | ConvolveVertically<false>(filter_values, filter_length, |
| 328 | first_row_for_filter, |
| 329 | filter_x.num_values(), cur_output_row); |
| 330 | } |
| 331 | } |
| 332 | } |
| 333 | |
deanm@google.com | a75222b | 2008-08-13 20:32:07 +0900 | [diff] [blame] | 334 | } // namespace gfx |
license.bot | f003cfe | 2008-08-24 09:55:55 +0900 | [diff] [blame^] | 335 | |