cachesim/utilities.c

   1 //
   2 //  utilities.c
   3 //  simpleADL
   4 //
   5 //  Created by pete on 1/17/17.
   6 //  Copyright © 2017 Kiva Design. All rights reserved.
   7 //
   8 // edited or touched Nov 6 2018
   9
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <sys/time.h>
  13
  14 #define EXTERN extern
  15 #include "utilities.h"
  16 #include "types.h"
  17
  18 static char * title = "kiva utility functions 1.0v6 [June 10 2019]";
  19
  20 /*
  21  1.0v6 [June 10 2019]
  22  - added btName() to give names to the types of blocks and queues
  23  1.0v5 [April 7 2018]
  24  - added isqrt() [validated elsewhere]
  25  1.0v4 [May 2017]
  26  - added teqFree()
  27  1.0v3
  28  - added teqAlloc()
  29  - by default utilityReport now set to 0
  30  1.0v2 May 2017
  31  - added char * utGetNameFromPath(char * p)
  32  1.0v1
  33  - initial version
  34  */
  35
  36
  37
  38 // ---------------- utilityTitleAndVersion ------------------
  39
  40 char * utilityTitleAndVersion(void) {
  41         return title;
  42 }
  43
  44 // -------------- findent -----------------
  45
  46 void findent(FILE * f, int depth) {
  47         // outputs 'indent' tabs after a newline
  48         fprintf(f, "\n");
  49         while (depth >= 0) {
  50                 fprintf(f, "\t");
  51                 depth--;
  52         }
  53 }
  54
  55 // ---------------- timenow ------------------
  56
  57 uint64 timenow(void) {
  58         // returns the current time in microseconds
  59         struct timeval tv;
  60         struct timezone tz;
  61         uint64 thetime;
  62         gettimeofday(&tv, &tz);
  63         thetime = ((uint64)tv.tv_sec * 1000000) + (uint64)tv.tv_usec;
  64         return thetime;
  65 }
  66
  67
  68 // -------------------- utGetNameFromPath ------------------
  69
  70 char * utGetNameFromPath(char * p) {
  71         char * path = strdup(p);
  72         // extract the last slice of the path to give the name
  73         uint32 len = (uint32)strlen(path);
  74         char * ptr = &path[len];
  75         *ptr = '\0';
  76         // walk backwards till we find a '/'
  77         while (*ptr != '/') ptr--;
  78         char * name = strdup(ptr + 1);
  79         free(path);
  80         return name;
  81 }
  82
  83 // ---------------- comments on rn creation ----------------
  84
  85 /*
  86
  87  https://fr.mathworks.com/matlabcentral/fileexchange/8054-triangular-distributed-random-variable-generator?requestedDomain=true
  88
  89  %Script by Dr.Mongkut Piantanakulchai
  90  %To simulate the triangular distribution
  91  %Return a vector of random variable
  92  %The range of the value is between (a,b)
  93  %The mode is c (most probable value)
  94  %n is to total number of values generated
  95  %Example of using
  96  %X = trirnd(1,5,10,100000);
  97  % this will generate 100000 random numbers between 1 and 10 (where most probable
  98  % value is 5)
  99  % To visualize the result use the command
 100  % hist(X,50);
 101
 102  function X=trirnd(a,c,b,n)
 103  X=zeros(n,1);
 104  for i=1:n
 105  %Assume a<X<c
 106  z=rand;
 107  if sqrt(z*(b-a)*(c-a))+a<c
 108  X(i)=sqrt(z*(b-a)*(c-a))+a;
 109  else
 110  X(i)=b-sqrt((1-z)*(b-a)*(b-c));
 111  end
 112  end %for
 113  %hist(X,50); Remove this comment % to look at histogram of X
 114  end %function
 115
 116  */
 117
 118 // ----------------------- random numbers --------------------
 119
 120 #define rvM                     ((1L << 31) - 1L)
 121 #define rvd                     (16807L)
 122 #define rvquotient              (rvM / rvd)
 123 #define rvremainder     (rvM % rvd)
 124
 125 #define maxUniformStream (8)
 126
 127
 128 //*********** NOTE: a stream must never get the value 0, or it won't ever change *******
 129
 130 static uint32 RandomStreams[maxUniformStream + 1];
 131
 132 // ----------------------------- uniform ---------------
 133
 134 uint32 uniform(uint32 stream, uint32 base, uint32 limit) {
 135         uint32 result;
 136         /* returns a uniformly distributed rv in base..limit
 137          the smallest number returned is base
 138          the largest number returned is base + (limit - 1)
 139          base, limit MUST both be >= 0
 140          limit MUST be > base
 141          these are NOT checked in the runtime
 142          */
 143
 144         // ********* NOTE:  warnings about integer overflow in expressions in this function should be ignored.
 145
 146         result = RandomStreams[stream];
 147         result = (rvd * (result % rvquotient)) -
 148         (rvremainder * (result / rvquotient));
 149         if (result == 0) {
 150                 // kill any zero values
 151                 result = rvd;
 152         }
 153
 154         RandomStreams[stream] = result;
 155
 156         //printf("\n\t\tRAW rv= %d 0x%08lx", result, result);
 157
 158         // reduce the range of the value to base..limit
 159         result %= (limit - base);
 160         return (base + result);
 161 }
 162
 163 // ----------------- isqrt -----------------------
 164
 165 uint32 isqrt(uint32 n) {
 166         uint32 rem = 0;
 167         uint32 root = 0;
 168         uint32 i;
 169         // validated with simple tests
 170         for (i = 0; i < 16; i++) {
 171                 root <<= 1;
 172                 rem <<= 2;
 173                 rem += n >> 30;
 174                 n <<= 2;
 175
 176                 if (root < rem) {
 177                         root++;
 178                         rem -= root;
 179                         root++;
 180                 }
 181         }
 182         return root >> 1;
 183 }
 184
 185
 186 // ----------------- triangular -------------------
 187
 188 uint32 triangular(uint32 stream, uint32 base, uint32 limit, uint32 mode) {
 189         // creates a triangularly-distributed RN in the range base, limit with peak at mode
 190         // only works for values in 0..1 as fractions...
 191
 192         uint32 z = uniform(stream, base, limit);
 193         uint32 s = isqrt(z*(limit - base)*(mode - base)) + base;
 194
 195         if (s < mode) {
 196                 return s;
 197         }
 198         else {
 199                 return limit-isqrt((1-z)*(limit-base)*(limit-mode));
 200         }
 201
 202 }
 203 /* ---------------------- initUniform --------------------------------- */
 204
 205 void initUniform(void) {
 206         // initialise the seeds - must call before calling uniform
 207
 208         int32 i;
 209         for (i = 0; i < maxUniformStream; i++) {
 210                 RandomStreams[i] = i + 1;
 211         }
 212 }
 213
 214 // ------------- sext ---------------------
 215
 216 int64 sext(uint32 n, uint64 v) {
 217         // sign extends v assuming it has n bits of data
 218         int64 r;
 219 //      printf("\nsign extend '%lld' which comprises %d bits", v, n);
 220         int64 mask = -1LL;
 221         uint64 bit = (1LL << (n - 1));
 222 //      printf("\n\tbit = %lld", bit);
 223         if (v & bit) {
 224                 // need to sign extend
 225                 mask = mask << n;
 226 //              printf("\n\tmask = 0x%08llx", mask);
 227                 r = mask | v;
 228 //              printf("\n\tr = 0x%08llx %lld", r, r);
 229         }
 230         else {
 231                 // nope
 232                 r = v;
 233         }
 234         return r;
 235 }
 236
 237