Home | History | Annotate | Download | only in enc 
      1 // Copyright 2012 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 // Author: Jyrki Alakuijala (jyrki (at) google.com)
     11 //
     12 
     13 #ifndef WEBP_ENC_BACKWARD_REFERENCES_ENC_H_
     14 #define WEBP_ENC_BACKWARD_REFERENCES_ENC_H_
     15 
     16 #include <assert.h>
     17 #include <stdlib.h>
     18 #include "src/webp/types.h"
     19 #include "src/webp/format_constants.h"
     20 
     21 #ifdef __cplusplus
     22 extern "C" {
     23 #endif
     24 
     25 // The maximum allowed limit is 11.
     26 #define MAX_COLOR_CACHE_BITS 10
     27 
     28 // -----------------------------------------------------------------------------
     29 // PixOrCopy
     30 
     31 enum Mode {
     32   kLiteral,
     33   kCacheIdx,
     34   kCopy,
     35   kNone
     36 };
     37 
     38 typedef struct {
     39   // mode as uint8_t to make the memory layout to be exactly 8 bytes.
     40   uint8_t mode;
     41   uint16_t len;
     42   uint32_t argb_or_distance;
     43 } PixOrCopy;
     44 
     45 static WEBP_INLINE PixOrCopy PixOrCopyCreateCopy(uint32_t distance,
     46                                                  uint16_t len) {
     47   PixOrCopy retval;
     48   retval.mode = kCopy;
     49   retval.argb_or_distance = distance;
     50   retval.len = len;
     51   return retval;
     52 }
     53 
     54 static WEBP_INLINE PixOrCopy PixOrCopyCreateCacheIdx(int idx) {
     55   PixOrCopy retval;
     56   assert(idx >= 0);
     57   assert(idx < (1 << MAX_COLOR_CACHE_BITS));
     58   retval.mode = kCacheIdx;
     59   retval.argb_or_distance = idx;
     60   retval.len = 1;
     61   return retval;
     62 }
     63 
     64 static WEBP_INLINE PixOrCopy PixOrCopyCreateLiteral(uint32_t argb) {
     65   PixOrCopy retval;
     66   retval.mode = kLiteral;
     67   retval.argb_or_distance = argb;
     68   retval.len = 1;
     69   return retval;
     70 }
     71 
     72 static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) {
     73   return (p->mode == kLiteral);
     74 }
     75 
     76 static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) {
     77   return (p->mode == kCacheIdx);
     78 }
     79 
     80 static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) {
     81   return (p->mode == kCopy);
     82 }
     83 
     84 static WEBP_INLINE uint32_t PixOrCopyLiteral(const PixOrCopy* const p,
     85                                              int component) {
     86   assert(p->mode == kLiteral);
     87   return (p->argb_or_distance >> (component * 8)) & 0xff;
     88 }
     89 
     90 static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) {
     91   return p->len;
     92 }
     93 
     94 static WEBP_INLINE uint32_t PixOrCopyCacheIdx(const PixOrCopy* const p) {
     95   assert(p->mode == kCacheIdx);
     96   assert(p->argb_or_distance < (1U << MAX_COLOR_CACHE_BITS));
     97   return p->argb_or_distance;
     98 }
     99 
    100 static WEBP_INLINE uint32_t PixOrCopyDistance(const PixOrCopy* const p) {
    101   assert(p->mode == kCopy);
    102   return p->argb_or_distance;
    103 }
    104 
    105 // -----------------------------------------------------------------------------
    106 // VP8LHashChain
    107 
    108 #define HASH_BITS 18
    109 #define HASH_SIZE (1 << HASH_BITS)
    110 
    111 // If you change this, you need MAX_LENGTH_BITS + WINDOW_SIZE_BITS <= 32 as it
    112 // is used in VP8LHashChain.
    113 #define MAX_LENGTH_BITS 12
    114 #define WINDOW_SIZE_BITS 20
    115 // We want the max value to be attainable and stored in MAX_LENGTH_BITS bits.
    116 #define MAX_LENGTH ((1 << MAX_LENGTH_BITS) - 1)
    117 #if MAX_LENGTH_BITS + WINDOW_SIZE_BITS > 32
    118 #error "MAX_LENGTH_BITS + WINDOW_SIZE_BITS > 32"
    119 #endif
    120 
    121 typedef struct VP8LHashChain VP8LHashChain;
    122 struct VP8LHashChain {
    123   // The 20 most significant bits contain the offset at which the best match
    124   // is found. These 20 bits are the limit defined by GetWindowSizeForHashChain
    125   // (through WINDOW_SIZE = 1<<20).
    126   // The lower 12 bits contain the length of the match. The 12 bit limit is
    127   // defined in MaxFindCopyLength with MAX_LENGTH=4096.
    128   uint32_t* offset_length_;
    129   // This is the maximum size of the hash_chain that can be constructed.
    130   // Typically this is the pixel count (width x height) for a given image.
    131   int size_;
    132 };
    133 
    134 // Must be called first, to set size.
    135 int VP8LHashChainInit(VP8LHashChain* const p, int size);
    136 // Pre-compute the best matches for argb.
    137 int VP8LHashChainFill(VP8LHashChain* const p, int quality,
    138                       const uint32_t* const argb, int xsize, int ysize,
    139                       int low_effort);
    140 void VP8LHashChainClear(VP8LHashChain* const p);  // release memory
    141 
    142 static WEBP_INLINE int VP8LHashChainFindOffset(const VP8LHashChain* const p,
    143                                                const int base_position) {
    144   return p->offset_length_[base_position] >> MAX_LENGTH_BITS;
    145 }
    146 
    147 static WEBP_INLINE int VP8LHashChainFindLength(const VP8LHashChain* const p,
    148                                                const int base_position) {
    149   return p->offset_length_[base_position] & ((1U << MAX_LENGTH_BITS) - 1);
    150 }
    151 
    152 static WEBP_INLINE void VP8LHashChainFindCopy(const VP8LHashChain* const p,
    153                                               int base_position,
    154                                               int* const offset_ptr,
    155                                               int* const length_ptr) {
    156   *offset_ptr = VP8LHashChainFindOffset(p, base_position);
    157   *length_ptr = VP8LHashChainFindLength(p, base_position);
    158 }
    159 
    160 // -----------------------------------------------------------------------------
    161 // VP8LBackwardRefs (block-based backward-references storage)
    162 
    163 // maximum number of reference blocks the image will be segmented into
    164 #define MAX_REFS_BLOCK_PER_IMAGE 16
    165 
    166 typedef struct PixOrCopyBlock PixOrCopyBlock;   // forward declaration
    167 typedef struct VP8LBackwardRefs VP8LBackwardRefs;
    168 
    169 // Container for blocks chain
    170 struct VP8LBackwardRefs {
    171   int block_size_;               // common block-size
    172   int error_;                    // set to true if some memory error occurred
    173   PixOrCopyBlock* refs_;         // list of currently used blocks
    174   PixOrCopyBlock** tail_;        // for list recycling
    175   PixOrCopyBlock* free_blocks_;  // free-list
    176   PixOrCopyBlock* last_block_;   // used for adding new refs (internal)
    177 };
    178 
    179 // Initialize the object. 'block_size' is the common block size to store
    180 // references (typically, width * height / MAX_REFS_BLOCK_PER_IMAGE).
    181 void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size);
    182 // Release memory for backward references.
    183 void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs);
    184 
    185 // Cursor for iterating on references content
    186 typedef struct {
    187   // public:
    188   PixOrCopy* cur_pos;           // current position
    189   // private:
    190   PixOrCopyBlock* cur_block_;   // current block in the refs list
    191   const PixOrCopy* last_pos_;   // sentinel for switching to next block
    192 } VP8LRefsCursor;
    193 
    194 // Returns a cursor positioned at the beginning of the references list.
    195 VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs);
    196 // Returns true if cursor is pointing at a valid position.
    197 static WEBP_INLINE int VP8LRefsCursorOk(const VP8LRefsCursor* const c) {
    198   return (c->cur_pos != NULL);
    199 }
    200 // Move to next block of references. Internal, not to be called directly.
    201 void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c);
    202 // Move to next position, or NULL. Should not be called if !VP8LRefsCursorOk().
    203 static WEBP_INLINE void VP8LRefsCursorNext(VP8LRefsCursor* const c) {
    204   assert(c != NULL);
    205   assert(VP8LRefsCursorOk(c));
    206   if (++c->cur_pos == c->last_pos_) VP8LRefsCursorNextBlock(c);
    207 }
    208 
    209 // -----------------------------------------------------------------------------
    210 // Main entry points
    211 
    212 enum VP8LLZ77Type {
    213   kLZ77Standard = 1,
    214   kLZ77RLE = 2,
    215   kLZ77Box = 4
    216 };
    217 
    218 // Evaluates best possible backward references for specified quality.
    219 // The input cache_bits to 'VP8LGetBackwardReferences' sets the maximum cache
    220 // bits to use (passing 0 implies disabling the local color cache).
    221 // The optimal cache bits is evaluated and set for the *cache_bits parameter.
    222 // The return value is the pointer to the best of the two backward refs viz,
    223 // refs[0] or refs[1].
    224 VP8LBackwardRefs* VP8LGetBackwardReferences(
    225     int width, int height, const uint32_t* const argb, int quality,
    226     int low_effort, int lz77_types_to_try, int* const cache_bits,
    227     const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs_tmp1,
    228     VP8LBackwardRefs* const refs_tmp2);
    229 
    230 #ifdef __cplusplus
    231 }
    232 #endif
    233 
    234 #endif  // WEBP_ENC_BACKWARD_REFERENCES_ENC_H_
    235