nanocoat/include/sjme/inflate.h

   1 /* -*- Mode: C; indent-tabs-mode: t; tab-width: 4 -*-
   2 // ---------------------------------------------------------------------------
   3 // SquirrelJME
   4 //     Copyright (C) Stephanie Gawroriski <xer@multiphasicapps.net>
   5 // ---------------------------------------------------------------------------
   6 // SquirrelJME is under the Mozilla Public License Version 2.0.
   7 // See license.mkd for licensing and copyright information.
   8 // -------------------------------------------------------------------------*/
   9
  10 /**
  11  * Generic inflation interface.
  12  *
  13  * @since 2024/08/25
  14  */
  15
  16 #ifndef SQUIRRELJME_INFLATE_H
  17 #define SQUIRRELJME_INFLATE_H
  18
  19 #include "sjme/stdTypes.h"
  20 #include "sjme/error.h"
  21 #include "stream.h"
  22
  23 /* Anti-C++. */
  24 #ifdef __cplusplus
  25         #ifndef SJME_CXX_IS_EXTERNED
  26                 #define SJME_CXX_IS_EXTERNED
  27                 #define SJME_CXX_SQUIRRELJME_INFLATE_H
  28 extern "C"
  29 {
  30         #endif /* #ifdef SJME_CXX_IS_EXTERNED */
  31 #endif /* #ifdef __cplusplus */
  32
  33 /*--------------------------------------------------------------------------*/
  34
  35 /** The size of the input/output buffer. */
  36 #define SJME_INFLATE_IO_BUFFER_SIZE 2048
  37
  38 /** The mask for the input/output buffer position. */
  39 #define SJME_INFLATE_IO_BUFFER_MASK 2047
  40
  41 /** When the output buffer is considered saturated. */
  42 #define SJME_INFLATE_IO_BUFFER_SATURATED 1700
  43
  44 /** The maximum window size. */
  45 #define SJME_INFLATE_WINDOW_MAX_SIZE 32768
  46
  47 /** The window size. */
  48 #define SJME_INFLATE_WINDOW_SIZE 16384
  49
  50 /** The window mask. */
  51 #define SJME_INFLATE_WINDOW_MASK 32768
  52
  53 /** Maximum huffman tree size. */
  54 #define SJME_INFLATE_HUFF_STORAGE_SIZE 16383
  55
  56 /** The limit for code lengths. */
  57 #define SJME_INFLATE_CODE_LEN_LIMIT 19
  58
  59 /** The maximum number of bits in the code length tree. */
  60 #define SJME_INFLATE_CODE_LEN_MAX_BITS 15
  61
  62 /** The number of codes. */
  63 #define SJME_INFLATE_NUM_CODES 288
  64
  65 /** The maximum number of literal lengths. */
  66 #define SJME_INFLATE_NUM_LIT_LENS 287
  67
  68 /** The maximum number of distance lengths. */
  69 #define SJME_INFLATE_NUM_DIST_LENS 33
  70
  71
  72 /**
  73  * Zip bit reading mode.
  74  *
  75  * @since 2024/08/18
  76  */
  77 typedef enum sjme_inflate_order
  78 {
  79         /** Least significant bit. */
  80         SJME_INFLATE_LSB,
  81
  82         /** Most significant bit. */
  83         SJME_INFLATE_MSB,
  84 } sjme_inflate_order;
  85
  86 /**
  87  * Used to either peek or pop from the bit stream.
  88  *
  89  * @since 2024/08/20
  90  */
  91 typedef enum sjme_inflate_peek
  92 {
  93         /** Pop value. */
  94         SJME_INFLATE_POP,
  95
  96         /** Peek value. */
  97         SJME_INFLATE_PEEK,
  98 } sjme_inflate_peek;
  99
 100 /**
 101  * Which type of node is this in the tree?
 102  *
 103  * @since 2024/08/22
 104  */
 105 typedef enum sjme_inflate_huffNodeType
 106 {
 107         /** Unknown. */
 108         SJME_INFLATE_UNKNOWN,
 109
 110         /** Node. */
 111         SJME_INFLATE_NODE,
 112
 113         /** Leaf. */
 114         SJME_INFLATE_LEAF,
 115 } sjme_inflate_huffNodeType;
 116
 117 /**
 118  * The inflation step.
 119  *
 120  * @since 2024/08/17
 121  */
 122 typedef enum sjme_inflate_step
 123 {
 124         /** Parse BTYPE and determine how to continue. */
 125         SJME_INFLATE_STEP_CHECK_BTYPE,
 126
 127         /** Literal uncompressed data header. */
 128         SJME_INFLATE_STEP_LITERAL_HEADER,
 129
 130         /** Literal uncompressed data. */
 131         SJME_INFLATE_STEP_LITERAL_DATA,
 132
 133         /** Load in dynamic huffman table. */
 134         SJME_INFLATE_STEP_DYNAMIC_TABLE_LOAD,
 135
 136         /** Load in dynamic huffman table: Code length tree. */
 137         SJME_INFLATE_STEP_DYNAMIC_TABLE_LOAD_CODE_LEN,
 138
 139         /** Load in dynamic huffman table: Literal. */
 140         SJME_INFLATE_STEP_DYNAMIC_TABLE_LOAD_LITERAL,
 141
 142         /** Load in dynamic huffman table: Distance tree. */
 143         SJME_INFLATE_STEP_DYNAMIC_TABLE_LOAD_DISTANCE,
 144
 145         /** Fixed static huffman table. */
 146         SJME_INFLATE_STEP_FIXED_TABLE_INFLATE,
 147
 148         /** Inflate from a given huffman tree. */
 149         SJME_INFLATE_STEP_INFLATE_FROM_TREE,
 150
 151         /** Finished, nothing is left. */
 152         SJME_INFLATE_STEP_FINISHED,
 153 } sjme_inflate_step;
 154
 155 /**
 156  * Inflation buffer state.
 157  *
 158  * @since 2024/08/17
 159  */
 160 typedef struct sjme_inflate_buffer
 161 {
 162         /** The amount of data that is ready for processing. */
 163         sjme_jint ready;
 164
 165         /** The current read head. */
 166         sjme_jint readHead;
 167
 168         /** The current write head. */
 169         sjme_jint writeHead;
 170
 171         /** The buffer storage. */
 172         sjme_jubyte buffer[SJME_INFLATE_IO_BUFFER_SIZE];
 173
 174         /** Was EOF hit in this buffer? */
 175         sjme_jboolean hitEof;
 176
 177         /** The current bit buffer. */
 178         sjme_juint bitBuffer;
 179
 180         /** The amount of bits in the buffer. */
 181         sjme_juint bitCount;
 182 } sjme_inflate_buffer;
 183
 184 /**
 185  * The window for output inflated data.
 186  *
 187  * @since 2024/08/18
 188  */
 189 typedef struct sjme_inflate_window
 190 {
 191         /** The number of bytes in the window. */
 192         sjme_juint length;
 193
 194         /** The end position of the window. */
 195         sjme_juint end;
 196
 197         /** The window buffer. */
 198         sjme_jubyte window[SJME_INFLATE_WINDOW_SIZE];
 199 } sjme_inflate_window;
 200
 201 /**
 202  * Initial code length huffman tree building values.
 203  *
 204  * @since 2024/08/22
 205  */
 206 typedef struct sjme_inflate_huffInit
 207 {
 208         /** Literal length. */
 209         sjme_juint litLen;
 210
 211         /** Distance length. */
 212         sjme_juint distLen;
 213
 214         /** The code length count. */
 215         sjme_juint codeLen;
 216
 217         /** The raw code length bit values. */
 218         sjme_juint rawCodeLens[SJME_INFLATE_CODE_LEN_LIMIT];
 219 } sjme_inflate_huffInit;
 220
 221 /**
 222  * Huffman tree building parameters, used as input.
 223  *
 224  * @since 2024/08/22
 225  */
 226 typedef struct sjme_inflate_huffParam
 227 {
 228         /** Code lengths to input. */
 229         sjme_juint* lengths;
 230
 231         /** The number of code lengths. */
 232         sjme_juint count;
 233 } sjme_inflate_huffParam;
 234
 235 /**
 236  * Huffman tree node.
 237  *
 238  * @since 2024/08/22
 239  */
 240 typedef struct sjme_align64 sjme_inflate_huffNode
 241         sjme_inflate_huffNode;
 242
 243 struct sjme_align64 sjme_inflate_huffNode
 244 {
 245         /** Node data. */
 246         union
 247         {
 248                 /** Data if a leaf. */
 249                 struct
 250                 {
 251                         /** Zero branch. */
 252                         sjme_inflate_huffNode* zero;
 253
 254                         /** One branch. */
 255                         sjme_inflate_huffNode* one;
 256                 } node;
 257
 258                 /** Data if a node. */
 259                 struct
 260                 {
 261                         /** The code stored here. */
 262                         sjme_juint code;
 263                 } leaf;
 264         } data;
 265
 266         /** Which type of node is this? */
 267         sjme_inflate_huffNodeType type;
 268 };
 269
 270 /**
 271  * Huffman tree parameters.
 272  *
 273  * @since 2024/08/20
 274  */
 275 typedef struct sjme_inflate_huffTree
 276 {
 277         /** The root node. */
 278         sjme_inflate_huffNode* root;
 279 } sjme_inflate_huffTree;
 280
 281 /**
 282  * Storage for huffman tree nodes.
 283  *
 284  * @since 2024/08/22
 285  */
 286 typedef struct sjme_inflate_huffTreeStorage
 287 {
 288         /** Storage for the huffman tree nodes. */
 289         sjme_align64 sjme_jubyte storage[SJME_INFLATE_HUFF_STORAGE_SIZE];
 290
 291         /** Next free node. */
 292         sjme_inflate_huffNode* next;
 293
 294         /** Final end of tree. */
 295         sjme_inflate_huffNode* finalEnd;
 296 } sjme_inflate_huffTreeStorage;
 297
 298 /**
 299  * Inflation state.
 300  *
 301  * @since 2024/08/17
 302  */
 303 typedef struct sjme_inflate_state sjme_inflate_state;
 304
 305 /**
 306  * Reads a code from the input.
 307  *
 308  * @param state The state to read from.
 309  * @param outCode The resultant code which was read.
 310  * @return On any error, if any.
 311  * @since 2024/08/25
 312  */
 313 typedef sjme_errorCode (*sjme_inflate_readCodeFunc)(
 314         sjme_attrInNotNull sjme_inflate_state* state,
 315         sjme_attrOutNotNull sjme_juint* outCode);
 316
 317 /**
 318  * Reads a distance code from the input.
 319  *
 320  * @param state The state to read from.
 321  * @param outDist The resultant distance code which was read.
 322  * @return On any error, if any.
 323  * @since 2024/08/25
 324  */
 325 typedef sjme_errorCode (*sjme_inflate_readDistFunc)(
 326         sjme_attrInNotNull sjme_inflate_state* state,
 327         sjme_attrOutNotNull sjme_juint* outDist);
 328
 329 /**
 330  * Inflation state.
 331  *
 332  * @since 2024/08/17
 333  */
 334 struct sjme_inflate_state
 335 {
 336         /** The current step in inflation. */
 337         sjme_inflate_step step;
 338
 339         /** Was the final block hit? */
 340         sjme_jboolean finalHit;
 341
 342         /** Is the input data corrupted? */
 343         sjme_jboolean invalidInput;
 344
 345         /** The output window. */
 346         sjme_inflate_window window;
 347
 348         /** The amount of literal bytes left to read. */
 349         sjme_jint literalLeft;
 350
 351         /** Initialization data for the initial huffman tree. */
 352         sjme_inflate_huffInit huffInit;
 353
 354         /** The function for reading codes. */
 355         sjme_inflate_readCodeFunc readCode;
 356
 357         /** The function for reading distances. */
 358         sjme_inflate_readDistFunc readDist;
 359
 360         /** Huffman tree node storage. */
 361         sjme_inflate_huffTreeStorage huffStorage;
 362
 363         /** Code length tree. */
 364         sjme_inflate_huffTree codeLenTree;
 365
 366         /** Distance tree. */
 367         sjme_inflate_huffTree distanceTree;
 368
 369         /** Literal tree, not literally. */
 370         sjme_inflate_huffTree literalTree;
 371
 372         /** The input buffer. */
 373         sjme_inflate_buffer input;
 374
 375         /** The output buffer. */
 376         sjme_inflate_buffer output;
 377 };
 378
 379 /**
 380  * Inflate stream initialization.
 381  *
 382  * @since 2024/08/17
 383  */
 384 typedef struct sjme_inflate_init
 385 {
 386         /** The compressed data stream. */
 387         sjme_stream_input handle;
 388
 389         /** Decompression state. */
 390         sjme_inflate_state* handleTwo;
 391 } sjme_inflate_init;
 392
 393 sjme_errorCode sjme_inflate_bitIn(
 394         sjme_attrInNotNull sjme_inflate_buffer* buffer,
 395         sjme_attrInValue sjme_inflate_order order,
 396         sjme_attrInValue sjme_inflate_peek popPeek,
 397         sjme_attrInRange(1, 32) sjme_juint bitCount,
 398         sjme_attrOutNotNull sjme_juint* readValue);
 399
 400 sjme_errorCode sjme_inflate_bitInCodeLen(
 401         sjme_attrInNotNull sjme_inflate_buffer* inBuffer,
 402         sjme_attrInNotNull sjme_inflate_huffTree* codeLenTree,
 403         sjme_attrInOutNotNull sjme_juint* index,
 404         sjme_attrOutNotNull sjme_juint* outLengths,
 405         sjme_attrInPositive sjme_juint count);
 406
 407 sjme_errorCode sjme_inflate_bitInTree(
 408         sjme_attrInNotNull sjme_inflate_buffer* inBuffer,
 409         sjme_attrInNotNull sjme_inflate_huffTree* fromTree,
 410         sjme_attrOutNotNull sjme_juint* outValue);
 411
 412 sjme_errorCode sjme_inflate_bitNeed(
 413         sjme_attrInNotNull sjme_inflate_buffer* buffer,
 414         sjme_attrInPositiveNonZero sjme_jint bitCount);
 415
 416 sjme_errorCode sjme_inflate_bitOut(
 417         sjme_attrInNotNull sjme_inflate_buffer* buffer,
 418         sjme_attrInValue sjme_inflate_order order,
 419         sjme_attrOutNotNull sjme_inflate_window* window,
 420         sjme_attrInRange(1, 32) sjme_juint bitCount,
 421         sjme_attrOutNotNull sjme_juint writeValue);
 422
 423 sjme_errorCode sjme_inflate_bufferArea(
 424         sjme_attrInNotNull sjme_inflate_buffer* buffer,
 425         sjme_attrOutNotNull sjme_jint* outRemainder,
 426         sjme_attrOutNotNull sjme_pointer* outBufOpPos,
 427         sjme_attrOutNotNull sjme_jint* outBufOpLen);
 428
 429 sjme_errorCode sjme_inflate_bufferConsume(
 430         sjme_attrInNotNull sjme_inflate_buffer* buffer,
 431         sjme_attrInPositiveNonZero sjme_jint count);
 432
 433 sjme_errorCode sjme_inflate_bufferGive(
 434         sjme_attrInNotNull sjme_inflate_buffer* buffer,
 435         sjme_attrInPositiveNonZero sjme_jint count);
 436
 437 sjme_errorCode sjme_inflate_decode(
 438         sjme_attrInNotNull sjme_inflate_state* state);
 439
 440 sjme_errorCode sjme_inflate_decodeBType(
 441         sjme_attrInNotNull sjme_inflate_state* state);
 442
 443 sjme_errorCode sjme_inflate_decodeDynLoad(
 444         sjme_attrInNotNull sjme_inflate_state* state);
 445
 446 sjme_errorCode sjme_inflate_decodeDynLoadCodeLen(
 447         sjme_attrInNotNull sjme_inflate_state* state);
 448
 449 sjme_errorCode sjme_inflate_decodeDynLoadLitDist(
 450         sjme_attrInNotNull sjme_inflate_state* state,
 451         sjme_attrInPositive sjme_juint count,
 452         sjme_attrInNotNull sjme_inflate_huffTree* outTree,
 453         sjme_attrInPositiveNonZero sjme_juint maxCount);
 454
 455 sjme_errorCode sjme_inflate_decodeLiteralData(
 456         sjme_attrInNotNull sjme_inflate_state* state);
 457
 458 sjme_errorCode sjme_inflate_decodeLiteralHeader(
 459         sjme_attrInNotNull sjme_inflate_state* state);
 460
 461 sjme_errorCode sjme_inflate_buildTree(
 462         sjme_attrInNotNull sjme_inflate_state* state,
 463         sjme_attrInNotNull sjme_inflate_huffParam* param,
 464         sjme_attrInNotNull sjme_inflate_huffTree* outTree,
 465         sjme_attrInNotNull sjme_inflate_huffTreeStorage* inStorage);
 466
 467 sjme_errorCode sjme_inflate_buildTreeInsert(
 468         sjme_attrInNotNull sjme_inflate_state* state,
 469         sjme_attrInNotNull sjme_inflate_huffTree* outTree,
 470         sjme_attrInNotNull sjme_inflate_huffTreeStorage* inStorage,
 471         sjme_attrInPositive sjme_juint code,
 472         sjme_attrInValue sjme_juint sym,
 473         sjme_attrInPositiveNonZero sjme_juint symMask);
 474
 475 sjme_errorCode sjme_inflate_buildTreeInsertNext(
 476         sjme_attrInNotNull sjme_inflate_huffTree* outTree,
 477         sjme_attrInNotNull sjme_inflate_huffTreeStorage* inStorage,
 478         sjme_attrOutNotNull sjme_inflate_huffNode** outNode);
 479
 480 sjme_errorCode sjme_inflate_processCodes(
 481         sjme_attrInNotNull sjme_inflate_state* state);
 482
 483 sjme_errorCode sjme_inflate_processDistance(
 484         sjme_attrInNotNull sjme_inflate_state* state,
 485         sjme_attrInNotNull sjme_inflate_buffer* inBuffer,
 486         sjme_attrInRange(257, 285) sjme_juint origCode,
 487         sjme_attrOutNotNull sjme_juint* outDist);
 488
 489 sjme_errorCode sjme_inflate_processLength(
 490         sjme_attrInNotNull sjme_inflate_state* state,
 491         sjme_attrInNotNull sjme_inflate_buffer* inBuffer,
 492         sjme_attrInRange(257, 285) sjme_juint code,
 493         sjme_attrOutNotNull sjme_juint* outLength);
 494
 495 sjme_errorCode sjme_inflate_processWindow(
 496         sjme_attrInNotNull sjme_inflate_state* state,
 497         sjme_attrInNotNull sjme_inflate_buffer* outBuffer,
 498         sjme_attrInNotNull sjme_inflate_window* window,
 499         sjme_attrInPositive sjme_juint windowDist,
 500         sjme_attrInPositive sjme_juint windowLen);
 501
 502 sjme_errorCode sjme_inflate_readCodeDynamic(
 503         sjme_attrInNotNull sjme_inflate_state* state,
 504         sjme_attrOutNotNull sjme_juint* outCode);
 505
 506 sjme_errorCode sjme_inflate_readDistDynamic(
 507         sjme_attrInNotNull sjme_inflate_state* state,
 508         sjme_attrOutNotNull sjme_juint* outDist);
 509
 510 sjme_errorCode sjme_inflate_readCodeFixed(
 511         sjme_attrInNotNull sjme_inflate_state* state,
 512         sjme_attrOutNotNull sjme_juint* outCode);
 513
 514 sjme_errorCode sjme_inflate_readDistFixed(
 515         sjme_attrInNotNull sjme_inflate_state* state,
 516         sjme_attrOutNotNull sjme_juint* outDist);
 517
 518 /*--------------------------------------------------------------------------*/
 519
 520 /* Anti-C++. */
 521 #ifdef __cplusplus
 522         #ifdef SJME_CXX_SQUIRRELJME_INFLATE_H
 523 }
 524                 #undef SJME_CXX_SQUIRRELJME_INFLATE_H
 525                 #undef SJME_CXX_IS_EXTERNED
 526         #endif /* #ifdef SJME_CXX_SQUIRRELJME_INFLATE_H */
 527 #endif /* #ifdef __cplusplus */
 528
 529 #endif /* SQUIRRELJME_INFLATE_H */