FFmpeg
mlz.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 Umair Khan <omerjerk@gmail.com>
3  *
4  * This file is part of FFmpeg.
5  *
6  * FFmpeg is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * FFmpeg is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with FFmpeg; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20 
21 #include "mlz.h"
22 
23 av_cold void ff_mlz_init_dict(void* context, MLZ *mlz) {
24  mlz->dict = av_mallocz_array(TABLE_SIZE, sizeof(*mlz->dict));
25 
26  mlz->flush_code = FLUSH_CODE;
29  mlz->bump_code = (DIC_INDEX_INIT - 1);
30  mlz->next_code = FIRST_CODE;
31  mlz->freeze_flag = 0;
32  mlz->context = context;
33 }
34 
36  MLZDict *dict = mlz->dict;
37  int i;
38  for ( i = 0; i < TABLE_SIZE; i++ ) {
39  dict[i].string_code = CODE_UNSET;
40  dict[i].parent_code = CODE_UNSET;
41  dict[i].match_len = 0;
42  }
44  mlz->dic_code_bit = CODE_BIT_INIT; // DicCodeBitInit;
45  mlz->bump_code = mlz->current_dic_index_max - 1;
46  mlz->next_code = FIRST_CODE;
47  mlz->freeze_flag = 0;
48 }
49 
50 static void set_new_entry_dict(MLZDict* dict, int string_code, int parent_code, int char_code) {
51  dict[string_code].parent_code = parent_code;
52  dict[string_code].string_code = string_code;
53  dict[string_code].char_code = char_code;
54  if (parent_code < FIRST_CODE) {
55  dict[string_code].match_len = 2;
56  } else {
57  dict[string_code].match_len = (dict[parent_code].match_len) + 1;
58  }
59 }
60 
61 static int decode_string(MLZ* mlz, unsigned char *buff, int string_code, int *first_char_code, unsigned long bufsize) {
62  MLZDict* dict = mlz->dict;
63  unsigned long count, offset;
64  int current_code, parent_code, tmp_code;
65 
66  count = 0;
67  current_code = string_code;
68  *first_char_code = CODE_UNSET;
69 
70  while (count < bufsize) {
71  switch (current_code) {
72  case CODE_UNSET:
73  return count;
74  break;
75  default:
76  if (current_code < FIRST_CODE) {
77  *first_char_code = current_code;
78  buff[0] = current_code;
79  count++;
80  return count;
81  } else {
82  offset = dict[current_code].match_len - 1;
83  tmp_code = dict[current_code].char_code;
84  if (offset >= bufsize) {
85  av_log(mlz->context, AV_LOG_ERROR, "MLZ offset error.\n");
86  return count;
87  }
88  buff[offset] = tmp_code;
89  count++;
90  }
91  current_code = dict[current_code].parent_code;
92  if ((current_code < 0) || (current_code > (DIC_INDEX_MAX - 1))) {
93  av_log(mlz->context, AV_LOG_ERROR, "MLZ dic index error.\n");
94  return count;
95  }
96  if (current_code > FIRST_CODE) {
97  parent_code = dict[current_code].parent_code;
98  offset = (dict[current_code].match_len) - 1;
99  if (parent_code < 0 || parent_code > DIC_INDEX_MAX-1) {
100  av_log(mlz->context, AV_LOG_ERROR, "MLZ dic index error.\n");
101  return count;
102  }
103  if (( offset > (DIC_INDEX_MAX - 1))) {
104  av_log(mlz->context, AV_LOG_ERROR, "MLZ dic offset error.\n");
105  return count;
106  }
107  }
108  break;
109  }
110  }
111  return count;
112 }
113 
114 static int input_code(GetBitContext* gb, int len) {
115  int tmp_code = 0;
116  int i;
117  for (i = 0; i < len; ++i) {
118  tmp_code |= get_bits1(gb) << i;
119  }
120  return tmp_code;
121 }
122 
123 int ff_mlz_decompression(MLZ* mlz, GetBitContext* gb, int size, unsigned char *buff) {
124  MLZDict *dict = mlz->dict;
125  unsigned long output_chars;
126  int string_code, last_string_code, char_code;
127 
128  string_code = 0;
129  char_code = -1;
130  last_string_code = -1;
131  output_chars = 0;
132 
133  while (output_chars < size) {
134  string_code = input_code(gb, mlz->dic_code_bit);
135  switch (string_code) {
136  case FLUSH_CODE:
137  case MAX_CODE:
138  ff_mlz_flush_dict(mlz);
139  char_code = -1;
140  last_string_code = -1;
141  break;
142  case FREEZE_CODE:
143  mlz->freeze_flag = 1;
144  break;
145  default:
146  if (string_code > mlz->current_dic_index_max) {
147  av_log(mlz->context, AV_LOG_ERROR, "String code %d exceeds maximum value of %d.\n", string_code, mlz->current_dic_index_max);
148  return output_chars;
149  }
150  if (string_code == (int) mlz->bump_code) {
151  ++mlz->dic_code_bit;
152  mlz->current_dic_index_max *= 2;
153  mlz->bump_code = mlz->current_dic_index_max - 1;
154  } else {
155  if (string_code >= mlz->next_code) {
156  int ret = decode_string(mlz, &buff[output_chars], last_string_code, &char_code, size - output_chars);
157  if (ret < 0 || ret > size - output_chars) {
158  av_log(mlz->context, AV_LOG_ERROR, "output chars overflow\n");
159  return output_chars;
160  }
161  output_chars += ret;
162  ret = decode_string(mlz, &buff[output_chars], char_code, &char_code, size - output_chars);
163  if (ret < 0 || ret > size - output_chars) {
164  av_log(mlz->context, AV_LOG_ERROR, "output chars overflow\n");
165  return output_chars;
166  }
167  output_chars += ret;
168  set_new_entry_dict(dict, mlz->next_code, last_string_code, char_code);
169  if (mlz->next_code >= TABLE_SIZE - 1) {
170  av_log(mlz->context, AV_LOG_ERROR, "Too many MLZ codes\n");
171  return output_chars;
172  }
173  mlz->next_code++;
174  } else {
175  int ret = decode_string(mlz, &buff[output_chars], string_code, &char_code, size - output_chars);
176  if (ret < 0 || ret > size - output_chars) {
177  av_log(mlz->context, AV_LOG_ERROR, "output chars overflow\n");
178  return output_chars;
179  }
180  output_chars += ret;
181  if (output_chars <= size && !mlz->freeze_flag) {
182  if (last_string_code != -1) {
183  set_new_entry_dict(dict, mlz->next_code, last_string_code, char_code);
184  if (mlz->next_code >= TABLE_SIZE - 1) {
185  av_log(mlz->context, AV_LOG_ERROR, "Too many MLZ codes\n");
186  return output_chars;
187  }
188  mlz->next_code++;
189  }
190  } else {
191  break;
192  }
193  }
194  last_string_code = string_code;
195  }
196  break;
197  }
198  }
199  return output_chars;
200 }
MLZDict::string_code
int string_code
Definition: mlz.h:39
ff_mlz_flush_dict
av_cold void ff_mlz_flush_dict(MLZ *mlz)
Flush the dictionary.
Definition: mlz.c:35
set_new_entry_dict
static void set_new_entry_dict(MLZDict *dict, int string_code, int parent_code, int char_code)
Definition: mlz.c:50
count
void INT64 INT64 count
Definition: avisynth_c.h:767
FREEZE_CODE
#define FREEZE_CODE
Definition: mlz.h:31
DIC_INDEX_INIT
#define DIC_INDEX_INIT
Definition: mlz.h:28
av_mallocz_array
void * av_mallocz_array(size_t nmemb, size_t size)
Definition: mem.c:191
DIC_INDEX_MAX
#define DIC_INDEX_MAX
Definition: mlz.h:29
MLZ
MLZ data strucure.
Definition: mlz.h:47
GetBitContext
Definition: get_bits.h:61
MLZDict::parent_code
int parent_code
Definition: mlz.h:40
MLZDict::char_code
int char_code
Definition: mlz.h:41
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
av_cold
#define av_cold
Definition: attributes.h:84
MLZ::freeze_flag
int freeze_flag
Definition: mlz.h:53
MLZ::context
void * context
Definition: mlz.h:55
MLZ::current_dic_index_max
int current_dic_index_max
Definition: mlz.h:49
decode_string
static int decode_string(MLZ *mlz, unsigned char *buff, int string_code, int *first_char_code, unsigned long bufsize)
Definition: mlz.c:61
mlz.h
context
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf default minimum maximum flags name is the option keep it simple and lowercase description are in without and describe what they for example set the foo of the bar offset is the offset of the field in your context
Definition: writing_filters.txt:91
get_bits1
static unsigned int get_bits1(GetBitContext *s)
Definition: get_bits.h:498
MLZ::next_code
int next_code
Definition: mlz.h:52
MLZDict
Dictionary structure for mlz decompression.
Definition: mlz.h:38
FIRST_CODE
#define FIRST_CODE
Definition: mlz.h:32
size
int size
Definition: twinvq_data.h:11134
offset
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf offset
Definition: writing_filters.txt:86
MLZDict::match_len
int match_len
Definition: mlz.h:42
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
CODE_BIT_INIT
#define CODE_BIT_INIT
Definition: mlz.h:27
FLUSH_CODE
#define FLUSH_CODE
Definition: mlz.h:30
MLZ::dic_code_bit
int dic_code_bit
Definition: mlz.h:48
len
int len
Definition: vorbis_enc_data.h:452
TABLE_SIZE
#define TABLE_SIZE
Definition: mlz.h:34
ret
ret
Definition: filter_design.txt:187
MLZ::dict
MLZDict * dict
Definition: mlz.h:54
ff_mlz_decompression
int ff_mlz_decompression(MLZ *mlz, GetBitContext *gb, int size, unsigned char *buff)
Run mlz decompression on the next size bits and the output will be stored in buff.
Definition: mlz.c:123
MLZ::bump_code
unsigned int bump_code
Definition: mlz.h:50
CODE_UNSET
#define CODE_UNSET
Definition: mlz.h:26
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:28
MAX_CODE
#define MAX_CODE
Definition: mlz.h:33
ff_mlz_init_dict
av_cold void ff_mlz_init_dict(void *context, MLZ *mlz)
Initialize the dictionary.
Definition: mlz.c:23
MLZ::flush_code
unsigned int flush_code
Definition: mlz.h:51
input_code
static int input_code(GetBitContext *gb, int len)
Definition: mlz.c:114