nanocoat/lib/base/circleBuffer.c

   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 #include <string.h>
  11
  12 #include "sjme/circleBuffer.h"
  13 #include "sjme/debug.h"
  14
  15 /**
  16  * Generic operation for circle buffers.
  17  *
  18  * @since 2024/08/25
  19  */
  20 typedef enum sjme_circleBuffer_operation
  21 {
  22         /** Push operation, queue. */
  23         SJME_CIRCLE_BUFFER_PUSH_QUEUE,
  24
  25         /** Push operation, window. */
  26         SJME_CIRCLE_BUFFER_PUSH_WINDOW,
  27
  28         /** Pop operation. */
  29         SJME_CIRCLE_BUFFER_POP,
  30
  31         /** Get operation. */
  32         SJME_CIRCLE_BUFFER_GET,
  33
  34         /** The number of operations that can be performed. */
  35         SJME_CIRCLE_BUFFER_NUM_OPERATIONS
  36 } sjme_circleBuffer_operation;
  37
  38 /**
  39  * A slice for accessing a buffer.
  40  *
  41  * @since 2024/08/25
  42  */
  43 typedef struct sjme_circleBuffer_slice
  44 {
  45         /** Non-circle buffer pointer? */
  46         sjme_pointer externalBuf;
  47
  48         /** The base position. */
  49         sjme_jint base;
  50
  51         /** The length. */
  52         sjme_jint len;
  53 } sjme_circleBuffer_slice;
  54
  55 /**
  56  * Stores the calculated result of the operation.
  57  *
  58  * @since 2024/08/25
  59  */
  60 typedef struct sjme_circleBuffer_calcResult
  61 {
  62         /** The new ready. */
  63         sjme_jint newReady;
  64
  65         /** The new write head. */
  66         sjme_jint newWriteHead;
  67
  68         /** The new read head. */
  69         sjme_jint newReadHead;
  70
  71         /** The source data slice. */
  72         sjme_circleBuffer_slice src[2];
  73
  74         /** The destination data slice. */
  75         sjme_circleBuffer_slice dest[2];
  76 } sjme_circleBuffer_calcResult;
  77
  78 static sjme_errorCode sjme_circleBuffer_splice(
  79         sjme_attrInNotNull sjme_circleBuffer* buffer,
  80         sjme_attrOutNotNull const sjme_circleBuffer_slice* circleSl,
  81         sjme_attrOutNotNull const sjme_circleBuffer_slice* externSl,
  82         sjme_attrOutNotNull const sjme_circleBuffer_slice* srcSl,
  83         sjme_attrOutNotNull const sjme_circleBuffer_slice* destSl,
  84         sjme_attrOutNotNull sjme_circleBuffer_calcResult* result)
  85 {
  86         sjme_circleBuffer_slice* circleAl;
  87         sjme_circleBuffer_slice* externAl;
  88         sjme_circleBuffer_slice* circleBl;
  89         sjme_circleBuffer_slice* externBl;
  90         sjme_circleBuffer_slice* tempXl;
  91         sjme_jint clipped, len, circleBase, externBase, limit;
  92
  93         if (buffer == NULL || circleSl == NULL || externSl == NULL ||
  94                 srcSl == NULL || destSl == NULL || result == NULL)
  95                 return SJME_ERROR_NULL_ARGUMENTS;
  96
  97         /* Common parameters used in the clipping algorithm. */
  98         circleBase = circleSl->base;
  99         externBase = externSl->base;
 100         len = circleSl->len;
 101
 102 #if 0
 103         /* Debug. */
 104         sjme_message("len: %d", len);
 105 #endif
 106
 107         /* Completely an inside slice? */
 108         if (circleBase >= 0 && circleBase < buffer->size &&
 109                 circleBase + len <= buffer->size)
 110         {
 111                 result->src[0] = *srcSl;
 112                 result->dest[0] = *destSl;
 113
 114                 return SJME_ERROR_NONE;
 115         }
 116
 117         /* Determine source and destination A and B sides to the slice. */
 118         if (srcSl == circleSl)
 119         {
 120                 circleAl = &result->src[0];
 121                 externAl = &result->dest[0];
 122                 circleBl = &result->src[1];
 123                 externBl = &result->dest[1];
 124         }
 125         else
 126         {
 127                 circleAl = &result->dest[0];
 128                 externAl = &result->src[0];
 129                 circleBl = &result->dest[1];
 130                 externBl = &result->src[1];
 131         }
 132
 133         /* External in opposite order? */
 134         if (circleBase < 0 && circleBase + len > 0)
 135         {
 136                 tempXl = externBl;
 137                 externBl = externAl;
 138                 externAl = tempXl;
 139         }
 140
 141         /* Left side slice? */
 142         if (circleBase < 0)
 143         {
 144                 clipped = 0 - circleBase;
 145
 146                 circleAl->base = 0;
 147                 circleAl->len = len - clipped;
 148                 externAl->base = 0;
 149                 externAl->len = len - clipped;
 150
 151                 circleBl->base = buffer->size - clipped;
 152                 circleBl->len = clipped;
 153                 externBl->base = len - clipped;
 154                 externBl->len = clipped;
 155         }
 156
 157         /* Right side slice? */
 158         else
 159         {
 160                 clipped = (circleBase + len) - buffer->size;
 161                 limit = buffer->size - circleBase;
 162
 163                 circleAl->base = circleBase;
 164                 circleAl->len = limit;
 165                 externAl->base = 0;
 166                 externAl->len = limit;
 167
 168                 circleBl->base = 0;
 169                 circleBl->len = clipped;
 170                 externBl->base = externBase + limit;
 171                 externBl->len = clipped;
 172         }
 173
 174         /* Propagate buffers. */
 175         externAl->externalBuf = externSl->externalBuf;
 176         externBl->externalBuf = externSl->externalBuf;
 177
 178         /* Success! */
 179         return SJME_ERROR_NONE;
 180 }
 181
 182 static sjme_errorCode sjme_circleBuffer_calc(
 183         sjme_attrInNotNull sjme_circleBuffer* buffer,
 184         sjme_attrOutNotNull sjme_circleBuffer_calcResult* result,
 185         sjme_attrInValue sjme_circleBuffer_operation operation,
 186         sjme_attrInNotNullBuf(length) sjme_pointer opData,
 187         sjme_attrInPositiveNonZero sjme_jint length,
 188         sjme_attrInValue sjme_circleBuffer_seekEnd seekType,
 189         sjme_attrInPositiveNonZero sjme_jint seekPos)
 190 {
 191         sjme_circleBuffer_slice circleSl;
 192         sjme_circleBuffer_slice externSl;
 193         sjme_circleBuffer_slice* srcSl;
 194         sjme_circleBuffer_slice* destSl;
 195
 196         if (buffer == NULL || result == NULL || opData == NULL)
 197                 return SJME_ERROR_NULL_ARGUMENTS;
 198
 199         if (seekType != SJME_CIRCLE_BUFFER_HEAD &&
 200                 seekType != SJME_CIRCLE_BUFFER_TAIL)
 201                 return SJME_ERROR_INVALID_ARGUMENT;
 202
 203         if (operation != SJME_CIRCLE_BUFFER_GET && seekPos != 0)
 204                 return SJME_ERROR_INVALID_ARGUMENT;
 205
 206         if (seekPos < 0 || length < 0 || (seekPos + length) < 0)
 207                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 208
 209         /* Clear result first. */
 210         memset(result, 0, sizeof(*result));
 211         memset(&circleSl, 0, sizeof(circleSl));
 212         memset(&externSl, 0, sizeof(externSl));
 213
 214         /* Default result parameters. */
 215         result->newReady = buffer->ready;
 216         result->newReadHead = buffer->readHead;
 217         result->newWriteHead = buffer->writeHead;
 218
 219         /* External slice is always set to the passed buffer. */
 220         externSl.externalBuf = opData;
 221         externSl.base = 0;
 222         externSl.len = length;
 223
 224         /* Circle slice is always the same length. */
 225         circleSl.len = length;
 226
 227         /* The window buffer can be pushed the same as a queue as long as it */
 228         /* does not exceed the buffer size. */
 229         if (operation == SJME_CIRCLE_BUFFER_PUSH_WINDOW)
 230                 if (buffer->ready + length <= buffer->size)
 231                         operation = SJME_CIRCLE_BUFFER_PUSH_QUEUE;
 232
 233         /* Pushing as a queue? */
 234         if (operation == SJME_CIRCLE_BUFFER_PUSH_QUEUE)
 235         {
 236                 /* External to circle. */
 237                 srcSl = &externSl;
 238                 destSl = &circleSl;
 239
 240                 /* Calculate new current data in the buffer. */
 241                 result->newReady = buffer->ready + length;
 242                 if (result->newReady > buffer->size)
 243                         return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 244
 245                 /* Writing at end? */
 246                 if (seekType == SJME_CIRCLE_BUFFER_LAST)
 247                 {
 248                         result->newWriteHead = buffer->writeHead + length;
 249                         circleSl.base = buffer->writeHead;
 250                 }
 251
 252                 /* Writing at start? */
 253                 else
 254                 {
 255                         result->newReadHead = buffer->readHead - length;
 256                         circleSl.base = result->newReadHead;
 257                 }
 258         }
 259
 260         /* Pushing as a window? */
 261         else if (operation == SJME_CIRCLE_BUFFER_PUSH_WINDOW)
 262         {
 263                 /* External to circle. */
 264                 srcSl = &externSl;
 265                 destSl = &circleSl;
 266
 267                 sjme_todo("Impl?");
 268                 return sjme_error_notImplemented(0);
 269         }
 270
 271         /* Popping? */
 272         else if (operation == SJME_CIRCLE_BUFFER_POP)
 273         {
 274                 /* Circle to external. */
 275                 srcSl = &circleSl;
 276                 destSl = &externSl;
 277
 278                 /* Calculate new size. */
 279                 result->newReady = buffer->ready - length;
 280                 if (result->newReady < 0)
 281                         return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 282
 283                 /* Removing from end? */
 284                 if (seekType == SJME_CIRCLE_BUFFER_LAST)
 285                 {
 286                         result->newWriteHead = buffer->writeHead - length;
 287                         circleSl.base = result->newWriteHead;
 288                 }
 289
 290                 /* Removing from start? */
 291                 else
 292                 {
 293                         result->newReadHead = buffer->readHead + length;
 294                         circleSl.base = buffer->readHead;
 295                 }
 296         }
 297
 298         /* Getting? */
 299         else if (operation == SJME_CIRCLE_BUFFER_GET)
 300         {
 301                 /* Circle to external. */
 302                 srcSl = &circleSl;
 303                 destSl = &externSl;
 304
 305                 /* The positions in the circle buffer are relative to the heads. */
 306                 if (seekType == SJME_CIRCLE_BUFFER_LAST)
 307                 {
 308                         /* Cannot get more data than what exists in the buffer. */
 309                         if ((buffer->ready - seekPos) + length > buffer->ready)
 310                                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 311
 312                         circleSl.base = buffer->writeHead - seekPos;
 313                 }
 314                 else
 315                 {
 316                         /* Cannot get more data than what exists in the buffer. */
 317                         if (seekPos + length > buffer->ready)
 318                                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 319
 320                         circleSl.base = buffer->readHead + seekPos;
 321                 }
 322         }
 323
 324         /* Invalid. */
 325         else
 326                 return SJME_ERROR_INVALID_ARGUMENT;
 327
 328         /* Make sure the read/write heads are in range. */
 329         while (result->newReadHead < 0)
 330                 result->newReadHead += buffer->size;
 331         while (result->newReadHead >= buffer->size)
 332                 result->newReadHead -= buffer->size;
 333         while (result->newWriteHead < 0)
 334                 result->newWriteHead += buffer->size;
 335         while (result->newWriteHead >= buffer->size)
 336                 result->newWriteHead -= buffer->size;
 337
 338         /* Perform splice clipping. */
 339         return sjme_circleBuffer_splice(buffer, &circleSl, &externSl,
 340                 srcSl, destSl, result);
 341 }
 342
 343 static sjme_errorCode sjme_circleBuffer_operate(
 344         sjme_attrInNotNull sjme_circleBuffer* buffer,
 345         sjme_attrInNotNull sjme_circleBuffer_calcResult* result)
 346 {
 347         sjme_jint i;
 348         sjme_circleBuffer_slice* src;
 349         sjme_circleBuffer_slice* dest;
 350
 351         if (buffer == NULL || result == NULL)
 352                 return SJME_ERROR_NULL_ARGUMENTS;
 353
 354         /* These must be in range. */
 355         if (result->newReady < 0 || result->newReady > buffer->size ||
 356                 result->newReadHead < 0 || result->newReadHead > buffer->size ||
 357                 result->newWriteHead < 0 || result->newWriteHead > buffer->size)
 358                 return SJME_ERROR_ILLEGAL_STATE;
 359
 360         /* Copy each slice, if valid. */
 361         for (i = 0; i < 2; i++)
 362         {
 363                 src = &result->src[i];
 364                 dest = &result->dest[i];
 365
 366                 /* Skip if nothing here. */
 367                 if (src->len == 0 && dest->len == 0)
 368                         continue;
 369
 370                 /* Length cannot be negative! */
 371                 if (src->len < 0 || dest->len < 0)
 372                         return SJME_ERROR_ILLEGAL_STATE;
 373
 374                 /* Fail if both external or both internal. */
 375                 if ((src->externalBuf == NULL) == (dest->externalBuf == NULL))
 376                         return SJME_ERROR_ILLEGAL_STATE;
 377
 378                 /* These must always be the same. */
 379                 if (src->len != dest->len)
 380                         return SJME_ERROR_ILLEGAL_STATE;
 381
 382 #if 0
 383                 /* Debug. */
 384                 sjme_message("Slice %d [%p %d %d] <- [%p %d %d]",
 385                         i, dest->externalBuf, dest->base, dest->len,
 386                         src->externalBuf, src->base, src->len);
 387 #endif
 388
 389                 /* External to internal. */
 390                 if (src->externalBuf != NULL && dest->externalBuf == NULL)
 391                         memmove(&buffer->buffer[dest->base],
 392                                 SJME_POINTER_OFFSET(src->externalBuf, src->base),
 393                                 src->len);
 394
 395                 /* Internal to external. */
 396                 else if (src->externalBuf == NULL && dest->externalBuf != NULL)
 397                         memmove(SJME_POINTER_OFFSET(dest->externalBuf, dest->base),
 398                                 &buffer->buffer[src->base],
 399                                 src->len);
 400
 401                 /* Should not occur. */
 402                 else
 403                         return SJME_ERROR_ILLEGAL_STATE;
 404         }
 405
 406         /* Set new heads. */
 407         buffer->ready = result->newReady;
 408         buffer->readHead = result->newReadHead;
 409         buffer->writeHead = result->newWriteHead;
 410
 411         /* Success! */
 412         return SJME_ERROR_NONE;
 413 }
 414
 415 sjme_errorCode sjme_circleBuffer_available(
 416         sjme_attrInNotNull sjme_circleBuffer* buffer,
 417         sjme_attrOutNotNull sjme_jint* outAvailable)
 418 {
 419         if (buffer == NULL || outAvailable == NULL)
 420                 return SJME_ERROR_NULL_ARGUMENTS;
 421
 422         *outAvailable = buffer->size - buffer->ready;
 423         return SJME_ERROR_NONE;
 424 }
 425
 426 sjme_errorCode sjme_circleBuffer_destroy(
 427         sjme_attrInNotNull sjme_circleBuffer* buffer)
 428 {
 429         sjme_errorCode error;
 430
 431         if (buffer == NULL)
 432                 return SJME_ERROR_NULL_ARGUMENTS;
 433
 434         /* Free storage first. */
 435         if (buffer->buffer != NULL)
 436         {
 437                 if (sjme_error_is(error = sjme_alloc_free(buffer->buffer)))
 438                         return sjme_error_default(error);
 439                 buffer->buffer = NULL;
 440         }
 441
 442         /* Then the buffer info. */
 443         return sjme_alloc_free(buffer);
 444 }
 445
 446 sjme_errorCode sjme_circleBuffer_get(
 447         sjme_attrInNotNull sjme_circleBuffer* buffer,
 448         sjme_attrOutNotNullBuf(outDataLen) sjme_pointer outData,
 449         sjme_attrInPositiveNonZero sjme_jint length,
 450         sjme_attrInValue sjme_circleBuffer_seekEnd seekType,
 451         sjme_attrInPositiveNonZero sjme_jint seekPos)
 452 {
 453         sjme_errorCode error;
 454         sjme_circleBuffer_calcResult result;
 455
 456         if (buffer == NULL)
 457                 return SJME_ERROR_NULL_ARGUMENTS;
 458
 459         if (length <= 0)
 460                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 461
 462         /* Calculate result. */
 463         memset(&result, 0, sizeof(result));
 464         if (sjme_error_is(error = sjme_circleBuffer_calc(
 465                 buffer, &result,
 466                 SJME_CIRCLE_BUFFER_GET,
 467                 outData, length, seekType, seekPos)))
 468                 return sjme_error_default(error);
 469
 470         /* Operate on it. */
 471         return sjme_circleBuffer_operate(buffer, &result);
 472 }
 473
 474 sjme_errorCode sjme_circleBuffer_new(
 475         sjme_attrInNotNull sjme_alloc_pool* inPool,
 476         sjme_attrOutNotNull sjme_circleBuffer** outBuffer,
 477         sjme_attrInValue sjme_circleBuffer_mode inMode,
 478         sjme_attrInPositiveNonZero sjme_jint length)
 479 {
 480         sjme_errorCode error;
 481         sjme_pointer storage;
 482         sjme_circleBuffer* result;
 483
 484         if (inPool == NULL || outBuffer == NULL)
 485                 return SJME_ERROR_NULL_ARGUMENTS;
 486
 487         if (inMode != SJME_CIRCLE_BUFFER_QUEUE &&
 488                 inMode != SJME_CIRCLE_BUFFER_WINDOW)
 489                 return SJME_ERROR_INVALID_ARGUMENT;
 490
 491         if (length <= 0)
 492                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 493
 494         /* Make sure we can allocate the buffer first. */
 495         storage = NULL;
 496         if (sjme_error_is(error = sjme_alloc(inPool,
 497                 length, (sjme_pointer*)&storage)) || storage == NULL)
 498                 goto fail_allocStorage;
 499
 500         /* Then the actual buffer info. */
 501         result = NULL;
 502         if (sjme_error_is(error = sjme_alloc(inPool,
 503                 sizeof(*result), (sjme_pointer*)&result)) || result == NULL)
 504                 goto fail_allocResult;
 505
 506         /* Setup information. */
 507         result->size = length;
 508         result->mode = inMode;
 509         result->buffer = storage;
 510
 511         /* Success! */
 512         *outBuffer = result;
 513         return SJME_ERROR_NONE;
 514
 515 fail_allocResult:
 516         if (result != NULL)
 517                 sjme_alloc_free(result);
 518 fail_allocStorage:
 519         if (storage != NULL)
 520                 sjme_alloc_free(storage);
 521
 522         return sjme_error_default(error);
 523 }
 524
 525 sjme_errorCode sjme_circleBuffer_pop(
 526         sjme_attrInNotNull sjme_circleBuffer* buffer,
 527         sjme_attrOutNotNullBuf(outDataLen) sjme_pointer outData,
 528         sjme_attrInPositiveNonZero sjme_jint length,
 529         sjme_attrInValue sjme_circleBuffer_seekEnd seekType)
 530 {
 531         sjme_errorCode error;
 532         sjme_circleBuffer_calcResult result;
 533
 534         if (buffer == NULL)
 535                 return SJME_ERROR_NULL_ARGUMENTS;
 536
 537         if (length <= 0)
 538                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 539
 540         /* Calculate result. */
 541         memset(&result, 0, sizeof(result));
 542         if (sjme_error_is(error = sjme_circleBuffer_calc(
 543                 buffer, &result,
 544                 SJME_CIRCLE_BUFFER_POP,
 545                 outData, length, seekType, 0)))
 546                 return sjme_error_default(error);
 547
 548         /* Operate on it. */
 549         return sjme_circleBuffer_operate(buffer, &result);
 550 }
 551
 552 sjme_errorCode sjme_circleBuffer_push(
 553         sjme_attrInNotNull sjme_circleBuffer* buffer,
 554         sjme_attrInNotNullBuf(outDataLen) sjme_cpointer inData,
 555         sjme_attrInPositiveNonZero sjme_jint length,
 556         sjme_attrInValue sjme_circleBuffer_seekEnd seekType)
 557 {
 558         sjme_errorCode error;
 559         sjme_circleBuffer_calcResult result;
 560
 561         if (buffer == NULL)
 562                 return SJME_ERROR_NULL_ARGUMENTS;
 563
 564         if (length <= 0)
 565                 return SJME_ERROR_INDEX_OUT_OF_BOUNDS;
 566
 567         /* Calculate result. */
 568         memset(&result, 0, sizeof(result));
 569         if (sjme_error_is(error = sjme_circleBuffer_calc(
 570                 buffer, &result,
 571                 (buffer->mode == SJME_CIRCLE_BUFFER_WINDOW ?
 572                         SJME_CIRCLE_BUFFER_PUSH_WINDOW : SJME_CIRCLE_BUFFER_PUSH_QUEUE),
 573                 inData, length, seekType, 0)))
 574                 return sjme_error_default(error);
 575
 576         /* Operate on it. */
 577         return sjme_circleBuffer_operate(buffer, &result);
 578 }
 579
 580 sjme_errorCode sjme_circleBuffer_stored(
 581         sjme_attrInNotNull sjme_circleBuffer* buffer,
 582         sjme_attrOutNotNull sjme_jint* outStored)
 583 {
 584         if (buffer == NULL || outStored == NULL)
 585                 return SJME_ERROR_NULL_ARGUMENTS;
 586
 587         *outStored = buffer->ready;
 588         return SJME_ERROR_NONE;
 589 }