1 /* 2 Copyright (C) 2009 Red Hat, Inc. 3 4 This library is free software; you can redistribute it and/or 5 modify it under the terms of the GNU Lesser General Public 6 License as published by the Free Software Foundation; either 7 version 2.1 of the License, or (at your option) any later version. 8 9 This library is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 Lesser General Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public 15 License along with this library; if not, see <http://www.gnu.org/licenses/>. 16 */ 17 18 #ifndef GLZ_ENCODER_PRIV_H_ 19 #define GLZ_ENCODER_PRIV_H_ 20 21 #include <pthread.h> 22 #include <common/lz_common.h> 23 24 #include "glz-encoder-dict.h" 25 26 /* Interface for using the dictionary for encoding. 27 Data structures are exposed for the encoder for efficiency 28 purposes. */ 29 typedef struct WindowImage WindowImage; 30 typedef struct WindowImageSegment WindowImageSegment; 31 32 33 //#define CHAINED_HASH 34 35 #ifdef CHAINED_HASH 36 #define HASH_SIZE_LOG 16 37 #define HASH_CHAIN_SIZE 4 38 #else 39 #define HASH_SIZE_LOG 20 40 #define HASH_CHAIN_SIZE 1 41 #endif 42 43 #define HASH_SIZE (1 << HASH_SIZE_LOG) 44 #define HASH_MASK (HASH_SIZE - 1) 45 46 typedef struct HashEntry HashEntry; 47 48 typedef struct SharedDictionary SharedDictionary; 49 50 struct WindowImage { 51 uint64_t id; 52 LzImageType type; 53 int size; // in pixels 54 uint32_t first_seg; 55 GlzUsrImageContext *usr_context; 56 WindowImage* next; 57 uint8_t is_alive; 58 }; 59 60 #define MAX_IMAGE_SEGS_NUM (0xffffffff) 61 #define NULL_IMAGE_SEG_ID MAX_IMAGE_SEGS_NUM 62 #define INIT_IMAGE_SEGS_NUM 1000 63 64 /* Images can be separated into several chunks. The basic unit of the 65 dictionary window is one image segment. Each segment is encoded separately. 66 An encoded match can refer to only one segment.*/ 67 struct WindowImageSegment { 68 WindowImage *image; 69 void *lines; 70 void *lines_end; 71 uint32_t pixels_num; // Number of pixels in the segment 72 uint64_t pixels_so_far; // Total no. pixels passed through the window till this segment. 73 // NOTE - never use size delta independently. It should 74 // always be used with respect to a previous size delta 75 uint32_t next; 76 }; 77 78 79 struct HashEntry { 80 uint32_t image_seg_idx; 81 uint32_t ref_pix_idx; 82 }; 83 84 85 struct SharedDictionary { 86 struct { 87 /* The segments storage. A dynamic array. 88 By referring to a segment by its index, instead of address, 89 we save space in the hash entries (32bit instead of 64bit) */ 90 WindowImageSegment *segs; 91 uint32_t segs_quota; 92 93 /* The window is manged as a linked list rather than as a cyclic 94 array in order to keep the indices of the segments consistent 95 after reallocation */ 96 97 /* the window in a resolution of image segments */ 98 uint32_t used_segs_head; // the latest head 99 uint32_t used_segs_tail; 100 uint32_t free_segs_head; 101 102 uint32_t *encoders_heads; // Holds for each encoder (by id), the window head when 103 // it started the encoding. 104 // The head is NULL_IMAGE_SEG_ID when the encoder is 105 // not encoding. 106 107 /* the window in a resolution of images. But here the head contains the oldest head*/ 108 WindowImage* used_images_tail; 109 WindowImage* used_images_head; 110 WindowImage* free_images; 111 112 uint64_t pixels_so_far; 113 uint32_t size_limit; // max number of pixels in a window (per encoder) 114 } window; 115 116 /* Concurrency issues: the reading/writing of each entry field should be atomic. 117 It is allowed that the reading/writing of the whole entry won't be atomic, 118 since before we access a reference we check its validity*/ 119 #ifdef CHAINED_HASH 120 HashEntry htab[HASH_SIZE][HASH_CHAIN_SIZE]; 121 uint8_t htab_counter[HASH_SIZE]; //cyclic counter for the next entry in a chain to be assigned 122 #else 123 HashEntry htab[HASH_SIZE]; 124 #endif 125 126 uint64_t last_image_id; 127 uint32_t max_encoders; 128 pthread_mutex_t lock; 129 pthread_rwlock_t rw_alloc_lock; 130 GlzEncoderUsrContext *cur_usr; // each encoder has other context. 131 }; 132 133 /* 134 Add the image to the tail of the window. 135 If possible, release images from the head of the window. 136 Also perform concurrency related operations. 137 138 usr_image_context: when an image is released from the window due to capacity overflow, 139 usr_image_context is given as a parameter to the free_image callback. 140 141 image_head_dist : the number of images between the current image and the head of the 142 window that is associated with the encoder. 143 */ 144 WindowImage *glz_dictionary_pre_encode(uint32_t encoder_id, GlzEncoderUsrContext *usr, 145 SharedDictionary *dict, LzImageType image_type, 146 int image_width, int image_height, int image_stride, 147 uint8_t *first_lines, unsigned int num_first_lines, 148 GlzUsrImageContext *usr_image_context, 149 uint32_t *image_head_dist); 150 151 /* 152 Performs concurrency related operations. 153 If possible, release images from the head of the window. 154 */ 155 void glz_dictionary_post_encode(uint32_t encoder_id, GlzEncoderUsrContext *usr, 156 SharedDictionary *dict); 157 158 #define IMAGE_SEG_IS_EARLIER(dict, dst_seg, src_seg) ( \ 159 ((src_seg) == NULL_IMAGE_SEG_ID) || (((dst_seg) != NULL_IMAGE_SEG_ID) \ 160 && ((dict)->window.segs[(dst_seg)].pixels_so_far < \ 161 (dict)->window.segs[(src_seg)].pixels_so_far))) 162 163 164 #ifdef CHAINED_HASH 165 #define UPDATE_HASH(dict, hval, seg, pix) { \ 166 uint8_t tmp_count = (dict)->htab_counter[hval]; \ 167 (dict)->htab[hval][tmp_count].image_seg_idx = seg; \ 168 (dict)->htab[hval][tmp_count].ref_pix_idx = pix; \ 169 tmp_count = ((tmp_count) + 1) & (HASH_CHAIN_SIZE - 1); \ 170 dict->htab_counter[hval] = tmp_count; \ 171 } 172 #else 173 #define UPDATE_HASH(dict, hval, seg, pix) { \ 174 (dict)->htab[hval].image_seg_idx = seg; \ 175 (dict)->htab[hval].ref_pix_idx = pix; \ 176 } 177 #endif 178 179 /* checks if the reference segment is located in the range of the window 180 of the current encoder */ 181 #define REF_SEG_IS_VALID(dict, enc_id, ref_seg, src_seg) ( \ 182 ((ref_seg) == (src_seg)) || \ 183 ((ref_seg)->image && \ 184 (ref_seg)->image->is_alive && \ 185 (src_seg->image->type == ref_seg->image->type) && \ 186 (ref_seg->pixels_so_far <= src_seg->pixels_so_far) && \ 187 ((dict)->window.segs[ \ 188 (dict)->window.encoders_heads[enc_id]].pixels_so_far <= \ 189 ref_seg->pixels_so_far))) 190 191 #ifdef DEBUG 192 193 #define GLZ_ASSERT(usr, x) \ 194 if (!(x)) (usr)->error(usr, "%s: ASSERT %s failed\n", __FUNCTION__, #x); 195 196 #else 197 198 #define GLZ_ASSERT(usr, x) 199 200 #endif 201 202 203 #endif /* GLZ_ENCODER_PRIV_H_ */ 204