Mu - 301array-equal.subx

1 # Comparing arrays of numbers. 2 3 == code 4 5 array-equal?: # a: (addr array int), b: (addr array int) -> result/eax: boolean 6 # pseudocode: 7 # asize = a->size 8 # if (asize != b->size) return false 9 # i = 0 10 # curra = a->data 11 # currb = b->data 12 # while i < asize 13 # i1 = *curra 14 # i2 = *currb 15 # if (c1 != c2) return false 16 # i+=4, curra+=4, currb+=4 17 # return true 18 # 19 # registers: 20 # i: ecx 21 # asize: edx 22 # curra: esi 23 # currb: edi 24 # i1: eax 25 # i2: ebx 26 # 27 # . prologue 28 55/push-ebp 29 89/<- %ebp 4/r32/esp 30 # . save registers 31 51/push-ecx 32 52/push-edx 33 53/push-ebx 34 56/push-esi 35 57/push-edi 36 # esi = a 37 8b/-> *(ebp+8) 6/r32/esi 38 # edi = b 39 8b/-> *(ebp+0xc) 7/r32/edi 40 # var asize/edx: int = a->size 41 8b/-> *esi 2/r32/edx 42 $array-equal?:sizes: 43 # if (asize != b->size) return false 44 39/compare *edi 2/r32/edx 45 75/jump-if-!= $array-equal?:false/disp8 46 # var curra/esi: (addr byte) = a->data 47 81 0/subop/add %esi 4/imm32 48 # var currb/edi: (addr byte) = b->data 49 81 0/subop/add %edi 4/imm32 50 # var i/ecx: int = 0 51 31/xor-with %ecx 1/r32/ecx 52 # var vala/eax: int 53 # var valb/ebx: int 54 $array-equal?:loop: 55 # if (i >= asize) return true 56 39/compare %ecx 2/r32/edx 57 7d/jump-if->= $array-equal?:true/disp8 58 # var vala/eax: int = *curra 59 8b/-> *esi 0/r32/eax 60 # var valb/ebx: int = *currb 61 8b/-> *edi 3/r32/ebx 62 # if (vala != valb) return false 63 39/compare %eax 3/r32/ebx 64 75/jump-if-!= $array-equal?:false/disp8 65 # i += 4 66 81 0/subop/add %ecx 4/imm32 67 # currs += 4 68 81 0/subop/add %esi 4/imm32 69 # currb += 4 70 81 0/subop/add %edi 4/imm32 71 eb/jump $array-equal?:loop/disp8 72 $array-equal?:true: 73 b8/copy-to-eax 1/imm32 74 eb/jump $array-equal?:end/disp8 75 $array-equal?:false: 76 b8/copy-to-eax 0/imm32 77 $array-equal?:end: 78 # . restore registers 79 5f/pop-to-edi 80 5e/pop-to-esi 81 5b/pop-to-ebx 82 5a/pop-to-edx 83 59/pop-to-ecx 84 # . epilogue 85 89/<- %esp 5/r32/ebp 86 5d/pop-to-ebp 87 c3/return 88 89 test-compare-empty-with-empty-array: 90 # . prologue 91 55/push-ebp 92 89/<- %ebp 4/r32/esp 93 # var ecx: (array _) = [] 94 68/push 0/imm32/size 95 89/<- %ecx 4/r32/esp 96 # var edx: (array _) = [] 97 68/push 0/imm32/size 98 89/<- %edx 4/r32/esp 99 # 100 (array-equal? %ecx %edx) # => eax 101 (check-ints-equal %eax 1 "F - test-compare-empty-with-empty-array") 102 # . epilogue 103 89/<- %esp 5/r32/ebp 104 5d/pop-to-ebp 105 c3/return 106 107 test-compare-empty-with-non-empty-array: # also checks size-mismatch code path 108 # . prologue 109 55/push-ebp 110 89/<- %ebp 4/r32/esp 111 # var ecx: (array int) = [1] 112 68/push 1/imm32 113 68/push 4/imm32/size 114 89/<- %ecx 4/r32/esp 115 # var edx: (array int) = [] 116 68/push 0/imm32/size 117 89/<- %edx 4/r32/esp 118 # 119 (array-equal? %ecx %edx) # => eax 120 (check-ints-equal %eax 0 "F - test-compare-empty-with-non-empty-array") 121 # . epilogue 122 89/<- %esp 5/r32/ebp 123 5d/pop-to-ebp 124 c3/return 125 126 test-compare-equal-arrays: 127 # . prologue 128 55/push-ebp 129 89/<- %ebp 4/r32/esp 130 # var ecx: (array int) = [1, 2, 3] 131 68/push 3/imm32 132 68/push 2/imm32 133 68/push 1/imm32 134 68/push 0xc/imm32/size 135 89/<- %ecx 4/r32/esp 136 # var edx: (array int) = [1, 2, 3] 137 68/push 3/imm32 138 68/push 2/imm32 139 68/push 1/imm32 140 68/push 0xc/imm32/size 141 89/<- %edx 4/r32/esp 142 # 143 (array-equal? %ecx %edx) # => eax 144 (check-ints-equal %eax 1 "F - test-compare-equal-arrays") 145 # . epilogue 146 89/<- %esp 5/r32/ebp 147 5d/pop-to-ebp 148 c3/return 149 150 test-compare-inequal-arrays-equal-sizes: 151 # . prologue 152 55/push-ebp 153 89/<- %ebp 4/r32/esp 154 # var ecx: (array int) = [1, 4, 3] 155 68/push 3/imm32 156 68/push 4/imm32 157 68/push 1/imm32 158 68/push 0xc/imm32/size 159 89/<- %ecx 4/r32/esp 160 # var edx: (array int) = [1, 2, 3] 161 68/push 3/imm32 162 68/push 2/imm32 163 68/push 1/imm32 164 68/push 0xc/imm32/size 165 89/<- %edx 4/r32/esp 166 # 167 (array-equal? %ecx %edx) # => eax 168 (check-ints-equal %eax 0 "F - test-compare-inequal-arrays-equal-sizes") 169 # . epilogue 170 89/<- %esp 5/r32/ebp 171 5d/pop-to-ebp 172 c3/return 173 174 _parse-array-of-ints: # ad: (addr allocation-descriptor), s: (addr array byte), out: (addr handle array int) 175 # pseudocode 176 # end = &s->data[s->size] 177 # curr = s->data 178 # size = 0 179 # while true 180 # if (curr >= end) break 181 # curr = skip-chars-matching-in-slice(curr, end, ' ') 182 # if (curr >= end) break 183 # curr = skip-chars-not-matching-in-slice(curr, end, ' ') 184 # ++size 185 # allocate-array(ad, size*4, out) 186 # var slice: slice = {s->data, 0} 187 # curr = lookup(out)->data 188 # while true 189 # if (slice->start >= end) break 190 # slice->start = skip-chars-matching-in-slice(slice->start, end, ' ') 191 # if (slice->start >= end) break 192 # slice->end = skip-chars-not-matching-in-slice(slice->start, end, ' ') 193 # *curr = parse-hex-int-from-slice(slice) 194 # curr += 4 195 # slice->start = slice->end 196 # return result 197 # 198 # . prologue 199 55/push-ebp 200 89/<- %ebp 4/r32/esp 201 # . save registers 202 50/push-eax 203 51/push-ecx 204 52/push-edx 205 53/push-ebx 206 56/push-esi 207 57/push-edi 208 # esi = s 209 8b/-> *(ebp+0xc) 6/r32/esi 210 # var curr/ecx: (addr byte) = s->data 211 8d/copy-address *(esi+4) 1/r32/ecx 212 # var end/edx: (addr byte) = &s->data[s->size] 213 # . edx = s->size 214 8b/-> *esi 2/r32/edx 215 # . edx += curr 216 01/add-to %edx 1/r32/ecx 217 # var size/ebx: int = 0 218 31/xor-with %ebx 3/r32/ebx 219 $_parse-array-of-ints:loop1: 220 # if (curr >= end) break 221 39/compare %ecx 2/r32/edx 222 73/jump-if-addr>= $_parse-array-of-ints:break1/disp8 223 # curr = skip-chars-matching-in-slice(curr, end, ' ') 224 (skip-chars-matching-in-slice %ecx %edx 0x20) # => eax 225 89/<- %ecx 0/r32/eax 226 # if (curr >= end) break 227 39/compare %ecx 2/r32/edx 228 73/jump-if-addr>= $_parse-array-of-ints:break1/disp8 229 # curr = skip-chars-not-matching-in-slice(curr, end, ' ') 230 (skip-chars-not-matching-in-slice %ecx %edx 0x20) # => eax 231 89/<- %ecx 0/r32/eax 232 # size += 4 233 81 0/subop/add %ebx 4/imm32 234 eb/jump $_parse-array-of-ints:loop1/disp8 235 $_parse-array-of-ints:break1: 236 (allocate-array *(ebp+8) %ebx *(ebp+0x10)) 237 $_parse-array-of-ints:pass2: 238 # var slice/edi: slice = {s->data, 0} 239 68/push 0/imm32/end 240 8d/copy-address *(esi+4) 7/r32/edi 241 57/push-edi 242 89/<- %edi 4/r32/esp 243 # curr = lookup(out)->data 244 8b/-> *(ebp+0x10) 0/r32/eax 245 (lookup *eax *(eax+4)) # => eax 246 8d/copy-address *(eax+4) 1/r32/ecx 247 $_parse-array-of-ints:loop2: 248 # if (slice->start >= end) break 249 39/compare *edi 2/r32/edgt { color: #aa0000 } /* Generic.Traceback */ .highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */ .highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */ .highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */ .highlight .kp { color: #008800 } /* Keyword.Pseudo */ .highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */ .highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */ .highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */ .highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */ .highlight .na { color: #336699 } /* Name.Attribute */ .highlight .nb { color: #003388 } /* Name.Builtin */ .highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */ .highlight .no { color: #003366; font-weight: bold } /* Name.Constant */ .highlight .nd { color: #555555 } /* Name.Decorator */ .highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */ .highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */ .highlight .nl { color: #336699; font-style: italic } /* Name.Label */ .highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */ .highlight .py { color: #336699; font-weight: bold } /* Name.Property */ .highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */ .highlight .nv { color: #336699 } /* Name.Variable */ .highlight .ow { color: #008800 } /* Operator.Word */ .highlight .w { color: #bbbbbb } /* Text.Whitespace */ .highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */ .highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */ .highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */ .highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */ .highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */ .highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */ .highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */ .highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */ .highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */ .highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */ .highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */ .highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */ .highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */ .highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */ .highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */ .highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */ .highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */ .highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */ .highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */ .highlight .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */

/*
** $Id: ltable.c,v 2.32.1.2 2007/12/28 15:32:23 roberto Exp $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/


/*
** Implementation of tables (aka arrays, objects, or hash tables).
** Tables keep its elements in two parts: an array part and a hash part.
** Non-negative integer keys are all candidates to be kept in the array
** part. The actual size of the array is the largest `n' such that at
** least half the slots between 0 and n are in use.
** Hash uses a mix of chained scatter table with Brent's variation.
** A main invariant of these tables is that, if an element is not
** in its main position (i.e. the `original' position that its hash gives
** to it), then the colliding element is in its own main position.
** Hence even when the load factor reaches 100%, performance remains good.
*/

#include <math.h>
#include <string.h>

#define ltable_c
#define LUA_CORE

#include "lua.h"

#include "ldebug.h"
#include "ldo.h"
#include "lgc.h"
#include "lmem.h"
#include "lobject.h"
#include "lstate.h"
#include "ltable.h"


/*
** max size of array part is 2^MAXBITS
*/
#if LUAI_BITSINT > 26
#define MAXBITS		26
#else
#define MAXBITS		(LUAI_BITSINT-2)
#endif

#define MAXASIZE	(1 << MAXBITS)


#define hashpow2(t,n)      (gnode(t, lmod((n), sizenode(t))))
  
#define hashstr(t,str)  hashpow2(t, (str)->tsv.hash)
#define hashboolean(t,p)        hashpow2(t, p)


/*
** for some types, it is better to avoid modulus by power of 2, as
** they tend to have many 2 factors.
*/
#define hashmod(t,n)	(gnode(t, ((n) % ((sizenode(t)-1)|1))))


#define hashpointer(t,p)	hashmod(t, IntPoint(p))


/*
** number of ints inside a lua_Number
*/
#define numints		cast_int(sizeof(lua_Number)/sizeof(int))



#define dummynode		(&dummynode_)

static const Node dummynode_ = {
  {{NULL}, LUA_TNIL},  /* value */
  {{{NULL}, LUA_TNIL, NULL}}  /* key */
};


/*
** hash for lua_Numbers
*/
static Node *hashnum (const Table *t, lua_Number n) {
  unsigned int a[numints];
  int i;
  if (luai_numeq(n, 0))  /* avoid problems with -0 */
    return gnode(t, 0);
  memcpy(a, &n, sizeof(a));
  for (i = 1; i < numints; i++) a[0] += a[i];
  return hashmod(t, a[0]);
}



/*
** returns the `main' position of an element in a table (that is, the index
** of its hash value)
*/
static Node *mainposition (const Table *t, const TValue *key) {
  switch (ttype(key)) {
    case LUA_TNUMBER:
      return hashnum(t, nvalue(key));
    case LUA_TSTRING:
      return hashstr(t, rawtsvalue(key));
    case LUA_TBOOLEAN:
      return hashboolean(t, bvalue(key));
    case LUA_TLIGHTUSERDATA:
      return hashpointer(t, pvalue(key));
    default:
      return hashpointer(t, gcvalue(key));
  }
}


/*
** returns the index for `key' if `key' is an appropriate key to live in
** the array part of the table, -1 otherwise.
*/
static int arrayindex (const TValue *key) {
  if (ttisnumber(key)) {
    lua_Number n = nvalue(key);
    int k;
    lua_number2int(k, n);
    if (luai_numeq(cast_num(k), n))
      return k;
  }
  return -1