/*
* Copyright (c) Meta Platforms, Inc. and affiliates.
* All rights reserved.
*
* This source code is licensed under both the BSD-style license (found in the
* LICENSE file in the root directory of this source tree) and the GPLv2 (found
* in the COPYING file in the root directory of this source tree).
* You may select, at your option, one of the above-listed licenses.
*/

#include "seqgen.h"
#include "mem.h"
#include <string.h>

#define MIN(a, b)  ((a) < (b) ? (a) : (b))

static const size_t kMatchBytes = 128;

#define SEQ_rotl32(x,r) ((x << r) | (x >> (32 - r)))
static BYTE SEQ_randByte(unsigned* src)
{
   static const U32 prime1 = 2654435761U;
   static const U32 prime2 = 2246822519U;
   U32 rand32 = *src;
   rand32 *= prime1;
   rand32 ^= prime2;
   rand32  = SEQ_rotl32(rand32, 13);
   *src = rand32;
   return (BYTE)(rand32 >> 5);
}

SEQ_stream SEQ_initStream(unsigned seed)
{
   SEQ_stream stream;
   stream.state = 0;
   XXH64_reset(&stream.xxh, 0);
   stream.seed = seed;
   return stream;
}

/* Generates a single guard byte, then match length + 1 of a different byte,
* then another guard byte.
*/
static size_t SEQ_gen_matchLength(SEQ_stream* stream, unsigned value,
                                 SEQ_outBuffer* out)
{
   typedef enum {
       ml_first_byte = 0,
       ml_match_bytes,
       ml_last_byte,
   } ml_state;
   BYTE* const ostart = (BYTE*)out->dst;
   BYTE* const oend = ostart + out->size;
   BYTE* op = ostart + out->pos;

   switch ((ml_state)stream->state) {
   case ml_first_byte:
       /* Generate a single byte and pick a different byte for the match */
       if (op >= oend) {
           stream->bytesLeft = 1;
           break;
       }
       *op = SEQ_randByte(&stream->seed) & 0xFF;
       do {
           stream->saved = SEQ_randByte(&stream->seed) & 0xFF;
       } while (*op == stream->saved);
       ++op;
       /* State transition */
       stream->state = ml_match_bytes;
       stream->bytesLeft = value + 1;
   /* fall-through */
   case ml_match_bytes: {
       /* Copy matchLength + 1 bytes to the output buffer */
       size_t const setLength = MIN(stream->bytesLeft, (size_t)(oend - op));
       if (setLength > 0) {
           memset(op, stream->saved, setLength);
           op += setLength;
           stream->bytesLeft -= setLength;
       }
       if (stream->bytesLeft > 0)
           break;
       /* State transition */
       stream->state = ml_last_byte;
   }
   /* fall-through */
   case ml_last_byte:
       /* Generate a single byte and pick a different byte for the match */
       if (op >= oend) {
           stream->bytesLeft = 1;
           break;
       }
       do {
           *op = SEQ_randByte(&stream->seed) & 0xFF;
       } while (*op == stream->saved);
       ++op;
       /* State transition */
   /* fall-through */
   default:
       stream->state = 0;
       stream->bytesLeft = 0;
       break;
   }
   XXH64_update(&stream->xxh, ostart + out->pos, (op - ostart) - out->pos);
   out->pos = op - ostart;
   return stream->bytesLeft;
}

/* Saves the current seed then generates kMatchBytes random bytes >= 128.
* Generates literal length - kMatchBytes random bytes < 128.
* Generates another kMatchBytes using the saved seed to generate a match.
* This way the match is easy to find for the compressors.
*/
static size_t SEQ_gen_litLength(SEQ_stream* stream, unsigned value, SEQ_outBuffer* out)
{
   typedef enum {
       ll_start = 0,
       ll_run_bytes,
       ll_literals,
       ll_run_match,
   } ll_state;
   BYTE* const ostart = (BYTE*)out->dst;
   BYTE* const oend = ostart + out->size;
   BYTE* op = ostart + out->pos;

   switch ((ll_state)stream->state) {
   case ll_start:
       stream->state = ll_run_bytes;
       stream->saved = stream->seed;
       stream->bytesLeft = MIN(kMatchBytes, value);
   /* fall-through */
   case ll_run_bytes:
       while (stream->bytesLeft > 0 && op < oend) {
           *op++ = SEQ_randByte(&stream->seed) | 0x80;
           --stream->bytesLeft;
       }
       if (stream->bytesLeft > 0)
           break;
       /* State transition */
       stream->state = ll_literals;
       stream->bytesLeft = value - MIN(kMatchBytes, value);
   /* fall-through */
   case ll_literals:
       while (stream->bytesLeft > 0 && op < oend) {
           *op++ = SEQ_randByte(&stream->seed) & 0x7F;
           --stream->bytesLeft;
       }
       if (stream->bytesLeft > 0)
           break;
       /* State transition */
       stream->state = ll_run_match;
       stream->bytesLeft = MIN(kMatchBytes, value);
   /* fall-through */
   case ll_run_match: {
       while (stream->bytesLeft > 0 && op < oend) {
           *op++ = SEQ_randByte(&stream->saved) | 0x80;
           --stream->bytesLeft;
       }
       if (stream->bytesLeft > 0)
           break;
   }
   /* fall-through */
   default:
       stream->state = 0;
       stream->bytesLeft = 0;
       break;
   }
   XXH64_update(&stream->xxh, ostart + out->pos, (op - ostart) - out->pos);
   out->pos = op - ostart;
   return stream->bytesLeft;
}

/* Saves the current seed then generates kMatchBytes random bytes >= 128.
* Generates offset - kMatchBytes of zeros to get a large offset without
* polluting the hash tables.
* Generates another kMatchBytes using the saved seed to generate a with the
* required offset.
*/
static size_t SEQ_gen_offset(SEQ_stream* stream, unsigned value, SEQ_outBuffer* out)
{
   typedef enum {
       of_start = 0,
       of_run_bytes,
       of_offset,
       of_run_match,
   } of_state;
   BYTE* const ostart = (BYTE*)out->dst;
   BYTE* const oend = ostart + out->size;
   BYTE* op = ostart + out->pos;

   switch ((of_state)stream->state) {
   case of_start:
       stream->state = of_run_bytes;
       stream->saved = stream->seed;
       stream->bytesLeft = MIN(value, kMatchBytes);
   /* fall-through */
   case of_run_bytes: {
       while (stream->bytesLeft > 0 && op < oend) {
           *op++ = SEQ_randByte(&stream->seed) | 0x80;
           --stream->bytesLeft;
       }
       if (stream->bytesLeft > 0)
           break;
       /* State transition */
       stream->state = of_offset;
       stream->bytesLeft = value - MIN(value, kMatchBytes);
   }
   /* fall-through */
   case of_offset: {
       /* Copy matchLength + 1 bytes to the output buffer */
       size_t const setLength = MIN(stream->bytesLeft, (size_t)(oend - op));
       if (setLength > 0) {
           memset(op, 0, setLength);
           op += setLength;
           stream->bytesLeft -= setLength;
       }
       if (stream->bytesLeft > 0)
           break;
       /* State transition */
       stream->state = of_run_match;
       stream->bytesLeft = MIN(value, kMatchBytes);
   }
   /* fall-through */
   case of_run_match: {
       while (stream->bytesLeft > 0 && op < oend) {
           *op++ = SEQ_randByte(&stream->saved) | 0x80;
           --stream->bytesLeft;
       }
       if (stream->bytesLeft > 0)
           break;
   }
   /* fall-through */
   default:
       stream->state = 0;
       stream->bytesLeft = 0;
       break;
   }
   XXH64_update(&stream->xxh, ostart + out->pos, (op - ostart) - out->pos);
   out->pos = op - ostart;
   return stream->bytesLeft;
}

/* Returns the number of bytes left to generate.
* Must pass the same type/value until it returns 0.
*/
size_t SEQ_gen(SEQ_stream* stream, SEQ_gen_type type, unsigned value, SEQ_outBuffer* out)
{
   switch (type) {
       case SEQ_gen_ml: return SEQ_gen_matchLength(stream, value, out);
       case SEQ_gen_ll: return SEQ_gen_litLength(stream, value, out);
       case SEQ_gen_of: return SEQ_gen_offset(stream, value, out);
       case SEQ_gen_max: /* fall-through */
       default: return 0;
   }
}

/* Returns the xxhash of the data produced so far */
XXH64_hash_t SEQ_digest(SEQ_stream const* stream)
{
   return XXH64_digest(&stream->xxh);
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.