FFmpeg  4.0
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 }
Dictionary structure for mlz decompression.
Definition: mlz.h:38
int size
static int decode_string(MLZ *mlz, unsigned char *buff, int string_code, int *first_char_code, unsigned long bufsize)
Definition: mlz.c:61
#define DIC_INDEX_MAX
Definition: mlz.h:29
int dic_code_bit
Definition: mlz.h:48
static int input_code(GetBitContext *gb, int len)
Definition: mlz.c:114
#define av_cold
Definition: attributes.h:82
static void set_new_entry_dict(MLZDict *dict, int string_code, int parent_code, int char_code)
Definition: mlz.c:50
#define av_log(a,...)
#define FREEZE_CODE
Definition: mlz.h:31
MLZDict * dict
Definition: mlz.h:54
#define CODE_BIT_INIT
Definition: mlz.h:27
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
int parent_code
Definition: mlz.h:40
unsigned int bump_code
Definition: mlz.h:50
unsigned int flush_code
Definition: mlz.h:51
static const uint8_t offset[127][2]
Definition: vf_spp.c:92
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
int char_code
Definition: mlz.h:41
#define FIRST_CODE
Definition: mlz.h:32
MLZ data strucure.
Definition: mlz.h:47
av_cold void ff_mlz_init_dict(void *context, MLZ *mlz)
Initialize the dictionary.
Definition: mlz.c:23
#define CODE_UNSET
Definition: mlz.h:26
static unsigned int get_bits1(GetBitContext *s)
Definition: get_bits.h:321
#define FLUSH_CODE
Definition: mlz.h:30
#define DIC_INDEX_INIT
Definition: mlz.h:28
int match_len
Definition: mlz.h:42
int freeze_flag
Definition: mlz.h:53
int string_code
Definition: mlz.h:39
av_cold void ff_mlz_flush_dict(MLZ *mlz)
Flush the dictionary.
Definition: mlz.c:35
void * context
Definition: mlz.h:55
int current_dic_index_max
Definition: mlz.h:49
int len
void INT64 INT64 count
Definition: avisynth_c.h:690
#define MAX_CODE
Definition: mlz.h:33
#define TABLE_SIZE
Definition: mlz.h:34
int next_code
Definition: mlz.h:52
void * av_mallocz_array(size_t nmemb, size_t size)
Allocate a memory block for an array with av_mallocz().
Definition: mem.c:191