sync.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2009 The NASM Authors - All Rights Reserved
   4  *   See the file AUTHORS included with the NASM distribution for
   5  *   the specific copyright holders.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following
   9  *   conditions are met:
  10  *
  11  *   * Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  *   * Redistributions in binary form must reproduce the above
  14  *     copyright notice, this list of conditions and the following
  15  *     disclaimer in the documentation and/or other materials provided
  16  *     with the distribution.
  17  *
  18  *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  19  *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21  *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28  *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  29  *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  30  *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  *
  32  * ----------------------------------------------------------------------- */
  33
  34 /*
  35  * sync.c   the Netwide Disassembler synchronisation processing module
  36  */
  37
  38 #include "compiler.h"
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <limits.h>
  43 #include <inttypes.h>
  44
  45 #include "nasmlib.h"
  46 #include "sync.h"
  47
  48 #define SYNC_MAX 4096           /* max # of sync points (initial) */
  49
  50 /*
  51  * This lot manages the current set of sync points by means of a
  52  * heap (priority queue) structure.
  53  */
  54
  55 static struct Sync {
  56     uint32_t pos;
  57     uint32_t length;
  58 } *synx;
  59 static int max_synx, nsynx;
  60
  61 void init_sync(void)
  62 {
  63     max_synx = SYNC_MAX-1;
  64     synx = nasm_malloc(SYNC_MAX * sizeof(*synx));
  65     nsynx = 0;
  66 }
  67
  68 void add_sync(uint32_t pos, uint32_t length)
  69 {
  70     int i;
  71
  72     if (nsynx >= max_synx) {
  73         max_synx = (max_synx << 1)+1;
  74         synx = nasm_realloc(synx, (max_synx+1) * sizeof(*synx));
  75     }
  76
  77     nsynx++;
  78     synx[nsynx].pos = pos;
  79     synx[nsynx].length = length;
  80
  81     for (i = nsynx; i > 1; i /= 2) {
  82         if (synx[i / 2].pos > synx[i].pos) {
  83             struct Sync t;
  84             t = synx[i / 2];    /* structure copy */
  85             synx[i / 2] = synx[i];      /* structure copy again */
  86             synx[i] = t;        /* another structure copy */
  87         }
  88     }
  89 }
  90
  91 uint32_t next_sync(uint32_t position, uint32_t *length)
  92 {
  93     while (nsynx > 0 && synx[1].pos + synx[1].length <= position) {
  94         int i, j;
  95         struct Sync t;
  96         t = synx[nsynx];        /* structure copy */
  97         synx[nsynx] = synx[1];  /* structure copy */
  98         synx[1] = t;            /* ditto */
  99
 100         nsynx--;
 101
 102         i = 1;
 103         while (i * 2 <= nsynx) {
 104             j = i * 2;
 105             if (synx[j].pos < synx[i].pos &&
 106                 (j + 1 > nsynx || synx[j + 1].pos > synx[j].pos)) {
 107                 t = synx[j];    /* structure copy */
 108                 synx[j] = synx[i];      /* lots of these... */
 109                 synx[i] = t;    /* ...aren't there? */
 110                 i = j;
 111             } else if (j + 1 <= nsynx && synx[j + 1].pos < synx[i].pos) {
 112                 t = synx[j + 1];        /* structure copy */
 113                 synx[j + 1] = synx[i];  /* structure <yawn> copy */
 114                 synx[i] = t;    /* structure copy <zzzz....> */
 115                 i = j + 1;
 116             } else
 117                 break;
 118         }
 119     }
 120
 121     if (nsynx > 0) {
 122         if (length)
 123             *length = synx[1].length;
 124         return synx[1].pos;
 125     } else {
 126         if (length)
 127             *length = 0L;
 128         return 0;
 129     }
 130 }