external/public-domain/xz/dist/src/liblzma/common/outqueue.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       outqueue.c
   4 /// \brief      Output queue handling in multithreaded coding
   5 //
   6 //  Author:     Lasse Collin
   7 //
   8 //  This file has been put into the public domain.
   9 //  You can do whatever you want with this file.
  10 //
  11 ///////////////////////////////////////////////////////////////////////////////
  12
  13 #include "outqueue.h"
  14
  15
  16 /// This is to ease integer overflow checking: We may allocate up to
  17 /// 2 * LZMA_THREADS_MAX buffers and we need some extra memory for other
  18 /// data structures (that's the second /2).
  19 #define BUF_SIZE_MAX (UINT64_MAX / LZMA_THREADS_MAX / 2 / 2)
  20
  21
  22 static lzma_ret
  23 get_options(uint64_t *bufs_alloc_size, uint32_t *bufs_count,
  24                 uint64_t buf_size_max, uint32_t threads)
  25 {
  26         if (threads > LZMA_THREADS_MAX || buf_size_max > BUF_SIZE_MAX)
  27                 return LZMA_OPTIONS_ERROR;
  28
  29         // The number of buffers is twice the number of threads.
  30         // This wastes RAM but keeps the threads busy when buffers
  31         // finish out of order.
  32         //
  33         // NOTE: If this is changed, update BUF_SIZE_MAX too.
  34         *bufs_count = threads * 2;
  35         *bufs_alloc_size = *bufs_count * buf_size_max;
  36
  37         return LZMA_OK;
  38 }
  39
  40
  41 extern uint64_t
  42 lzma_outq_memusage(uint64_t buf_size_max, uint32_t threads)
  43 {
  44         uint64_t bufs_alloc_size;
  45         uint32_t bufs_count;
  46
  47         if (get_options(&bufs_alloc_size, &bufs_count, buf_size_max, threads)
  48                         != LZMA_OK)
  49                 return UINT64_MAX;
  50
  51         return sizeof(lzma_outq) + bufs_count * sizeof(lzma_outbuf)
  52                         + bufs_alloc_size;
  53 }
  54
  55
  56 extern lzma_ret
  57 lzma_outq_init(lzma_outq *outq, const lzma_allocator *allocator,
  58                 uint64_t buf_size_max, uint32_t threads)
  59 {
  60         uint64_t bufs_alloc_size;
  61         uint32_t bufs_count;
  62
  63         // Set bufs_count and bufs_alloc_size.
  64         return_if_error(get_options(&bufs_alloc_size, &bufs_count,
  65                         buf_size_max, threads));
  66
  67         // Allocate memory if needed.
  68         if (outq->buf_size_max != buf_size_max
  69                         || outq->bufs_allocated != bufs_count) {
  70                 lzma_outq_end(outq, allocator);
  71
  72 #if SIZE_MAX < UINT64_MAX
  73                 if (bufs_alloc_size > SIZE_MAX)
  74                         return LZMA_MEM_ERROR;
  75 #endif
  76
  77                 outq->bufs = lzma_alloc(bufs_count * sizeof(lzma_outbuf),
  78                                 allocator);
  79                 outq->bufs_mem = lzma_alloc((size_t)(bufs_alloc_size),
  80                                 allocator);
  81
  82                 if (outq->bufs == NULL || outq->bufs_mem == NULL) {
  83                         lzma_outq_end(outq, allocator);
  84                         return LZMA_MEM_ERROR;
  85                 }
  86         }
  87
  88         // Initialize the rest of the main structure. Initialization of
  89         // outq->bufs[] is done when they are actually needed.
  90         outq->buf_size_max = (size_t)(buf_size_max);
  91         outq->bufs_allocated = bufs_count;
  92         outq->bufs_pos = 0;
  93         outq->bufs_used = 0;
  94         outq->read_pos = 0;
  95
  96         return LZMA_OK;
  97 }
  98
  99
 100 extern void
 101 lzma_outq_end(lzma_outq *outq, const lzma_allocator *allocator)
 102 {
 103         lzma_free(outq->bufs, allocator);
 104         outq->bufs = NULL;
 105
 106         lzma_free(outq->bufs_mem, allocator);
 107         outq->bufs_mem = NULL;
 108
 109         return;
 110 }
 111
 112
 113 extern lzma_outbuf *
 114 lzma_outq_get_buf(lzma_outq *outq)
 115 {
 116         // Caller must have checked it with lzma_outq_has_buf().
 117         assert(outq->bufs_used < outq->bufs_allocated);
 118
 119         // Initialize the new buffer.
 120         lzma_outbuf *buf = &outq->bufs[outq->bufs_pos];
 121         buf->buf = outq->bufs_mem + outq->bufs_pos * outq->buf_size_max;
 122         buf->size = 0;
 123         buf->finished = false;
 124
 125         // Update the queue state.
 126         if (++outq->bufs_pos == outq->bufs_allocated)
 127                 outq->bufs_pos = 0;
 128
 129         ++outq->bufs_used;
 130
 131         return buf;
 132 }
 133
 134
 135 extern bool
 136 lzma_outq_is_readable(const lzma_outq *outq)
 137 {
 138         uint32_t i = outq->bufs_pos - outq->bufs_used;
 139         if (outq->bufs_pos < outq->bufs_used)
 140                 i += outq->bufs_allocated;
 141
 142         return outq->bufs[i].finished;
 143 }
 144
 145
 146 extern lzma_ret
 147 lzma_outq_read(lzma_outq *restrict outq, uint8_t *restrict out,
 148                 size_t *restrict out_pos, size_t out_size,
 149                 lzma_vli *restrict unpadded_size,
 150                 lzma_vli *restrict uncompressed_size)
 151 {
 152         // There must be at least one buffer from which to read.
 153         if (outq->bufs_used == 0)
 154                 return LZMA_OK;
 155
 156         // Get the buffer.
 157         uint32_t i = outq->bufs_pos - outq->bufs_used;
 158         if (outq->bufs_pos < outq->bufs_used)
 159                 i += outq->bufs_allocated;
 160
 161         lzma_outbuf *buf = &outq->bufs[i];
 162
 163         // If it isn't finished yet, we cannot read from it.
 164         if (!buf->finished)
 165                 return LZMA_OK;
 166
 167         // Copy from the buffer to output.
 168         lzma_bufcpy(buf->buf, &outq->read_pos, buf->size,
 169                         out, out_pos, out_size);
 170
 171         // Return if we didn't get all the data from the buffer.
 172         if (outq->read_pos < buf->size)
 173                 return LZMA_OK;
 174
 175         // The buffer was finished. Tell the caller its size information.
 176         *unpadded_size = buf->unpadded_size;
 177         *uncompressed_size = buf->uncompressed_size;
 178
 179         // Free this buffer for further use.
 180         --outq->bufs_used;
 181         outq->read_pos = 0;
 182
 183         return LZMA_STREAM_END;
 184 }