aboutsummaryrefslogtreecommitdiff
path: root/lib/lua/src/lgc.h
blob: 5a8dc605b319f5e1320f5b4be8f9156312b0327e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*
** $Id: lgc.h,v 2.15.1.1 2007/12/27 13:02:25 roberto Exp $
** Garbage Collector
** See Copyright Notice in lua.h
*/

#ifndef lgc_h
#define lgc_h


#include "lobject.h"


/*
** Possible states of the Garbage Collector
*/
#define GCSpause	0
#define GCSpropagate	1
#define GCSsweepstring	2
#define GCSsweep	3
#define GCSfinalize	4


/*
** some userful bit tricks
*/
#define resetbits(x,m)	((x) &= cast(lu_byte, ~(m)))
#define setbits(x,m)	((x) |= (m))
#define testbits(x,m)	((x) & (m))
#define bitmask(b)	(1<<(b))
#define bit2mask(b1,b2)	(bitmask(b1) | bitmask(b2))
#define l_setbit(x,b)	setbits(x, bitmask(b))
#define resetbit(x,b)	resetbits(x, bitmask(b))
#define testbit(x,b)	testbits(x, bitmask(b))
#define set2bits(x,b1,b2)	setbits(x, (bit2mask(b1, b2)))
#define reset2bits(x,b1,b2)	resetbits(x, (bit2mask(b1, b2)))
#define test2bits(x,b1,b2)	testbits(x, (bit2mask(b1, b2)))



/*
** Layout for bit use in `marked' field:
** bit 0 - object is white (type 0)
** bit 1 - object is white (type 1)
** bit 2 - object is black
** bit 3 - for userdata: has been finalized
** bit 3 - for tables: has weak keys
** bit 4 - for tables: has weak values
** bit 5 - object is fixed (should not be collected)
** bit 6 - object is "super" fixed (only the main thread)
*/


#define WHITE0BIT	0
#define WHITE1BIT	1
#define BLACKBIT	2
#define FINALIZEDBIT	3
#define KEYWEAKBIT	3
#define VALUEWEAKBIT	4
#define FIXEDBIT	5
#define SFIXEDBIT	6
#define WHITEBITS	bit2mask(WHITE0BIT, WHITE1BIT)


#define iswhite(x)      test2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
#define isblack(x)      testbit((x)->gch.marked, BLACKBIT)
#define isgray(x)	(!isblack(x) && !iswhite(x))

#define otherwhite(g)	(g->currentwhite ^ WHITEBITS)
#define isdead(g,v)	((v)->gch.marked & otherwhite(g) & WHITEBITS)

#define changewhite(x)	((x)->gch.marked ^= WHITEBITS)
#define gray2black(x)	l_setbit((x)->gch.marked, BLACKBIT)

#define valiswhite(x)	(iscollectable(x) && iswhite(gcvalue(x)))

#define luaC_white(g)	cast(lu_byte, (g)->currentwhite & WHITEBITS)


#define luaC_checkGC(L) { \
  condhardstacktests(luaD_reallocstack(L, L->stacksize - EXTRA_STACK - 1)); \
  if (G(L)->totalbytes >= G(L)->GCthreshold) \
	luaC_step(L); }


#define luaC_barrier(L,p,v) { if (valiswhite(v) && isblack(obj2gco(p)))  \
	luaC_barrierf(L,obj2gco(p),gcvalue(v)); }

#define luaC_barriert(L,t,v) { if (valiswhite(v) && isblack(obj2gco(t)))  \
	luaC_barrierback(L,t); }

#define luaC_objbarrier(L,p,o)  \
	{ if (iswhite(obj2gco(o)) && isblack(obj2gco(p))) \
		luaC_barrierf(L,obj2gco(p),obj2gco(o)); }

#define luaC_objbarriert(L,t,o)  \
   { if (iswhite(obj2gco(o)) && isblack(obj2gco(t))) luaC_barrierback(L,t); }

LUAI_FUNC size_t luaC_separateudata (lua_State *L, int all);
LUAI_FUNC void luaC_callGCTM (lua_State *L);
LUAI_FUNC void luaC_freeall (lua_State *L);
LUAI_FUNC void luaC_step (lua_State *L);
LUAI_FUNC void luaC_fullgc (lua_State *L);
LUAI_FUNC void luaC_link (lua_State *L, GCObject *o, lu_byte tt);
LUAI_FUNC void luaC_linkupval (lua_State *L, UpVal *uv);
LUAI_FUNC void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v);
LUAI_FUNC void luaC_barrierback (lua_State *L, Table *t);


#endif
an> #include "noise.h" class TestRandom : public TestBase { public: TestRandom() { TestManager::registerTestModule(this); } const char *getName() { return "TestRandom"; } void runTests(IGameDef *gamedef); void testPseudoRandom(); void testPseudoRandomRange(); void testPcgRandom(); void testPcgRandomRange(); void testPcgRandomBytes(); void testPcgRandomNormalDist(); static const int expected_pseudorandom_results[256]; static const u32 expected_pcgrandom_results[256]; static const u8 expected_pcgrandom_bytes_result[24]; static const u8 expected_pcgrandom_bytes_result2[24]; }; static TestRandom g_test_instance; void TestRandom::runTests(IGameDef *gamedef) { TEST(testPseudoRandom); TEST(testPseudoRandomRange); TEST(testPcgRandom); TEST(testPcgRandomRange); TEST(testPcgRandomBytes); TEST(testPcgRandomNormalDist); } //////////////////////////////////////////////////////////////////////////////// void TestRandom::testPseudoRandom() { PseudoRandom pr(814538); for (u32 i = 0; i != 256; i++) UASSERTEQ(int, pr.next(), expected_pseudorandom_results[i]); } void TestRandom::testPseudoRandomRange() { PseudoRandom pr((int)time(NULL)); EXCEPTION_CHECK(PrngException, pr.range(2000, 6000)); EXCEPTION_CHECK(PrngException, pr.range(5, 1)); for (u32 i = 0; i != 32768; i++) { int min = (pr.next() % 3000) - 500; int max = (pr.next() % 3000) - 500; if (min > max) SWAP(int, min, max); int randval = pr.range(min, max); UASSERT(randval >= min); UASSERT(randval <= max); } } void TestRandom::testPcgRandom() { PcgRandom pr(814538, 998877); for (u32 i = 0; i != 256; i++) UASSERTEQ(u32, pr.next(), expected_pcgrandom_results[i]); } void TestRandom::testPcgRandomRange() { PcgRandom pr((int)time(NULL)); EXCEPTION_CHECK(PrngException, pr.range(5, 1)); // Regression test for bug 3027 pr.range(pr.RANDOM_MIN, pr.RANDOM_MAX); for (u32 i = 0; i != 32768; i++) { int min = (pr.next() % 3000) - 500; int max = (pr.next() % 3000) - 500; if (min > max) SWAP(int, min, max); int randval = pr.range(min, max); UASSERT(randval >= min); UASSERT(randval <= max); } } void TestRandom::testPcgRandomBytes() { char buf[32]; PcgRandom r(1538, 877); memset(buf, 0, sizeof(buf)); r.bytes(buf + 5, 23); UASSERT(memcmp(buf + 5, expected_pcgrandom_bytes_result, sizeof(expected_pcgrandom_bytes_result)) == 0); memset(buf, 0, sizeof(buf)); r.bytes(buf, 17); UASSERT(memcmp(buf, expected_pcgrandom_bytes_result2, sizeof(expected_pcgrandom_bytes_result2)) == 0); } void TestRandom::testPcgRandomNormalDist() { static const int max = 120; static const int min = -120; static const int num_trials = 20; static const u32 num_samples = 61000; s32 bins[max - min + 1]; memset(bins, 0, sizeof(bins)); PcgRandom r(486179 + (int)time(NULL)); for (u32 i = 0; i != num_samples; i++) { s32 randval = r.randNormalDist(min, max, num_trials); UASSERT(randval <= max); UASSERT(randval >= min); bins[randval - min]++; } // Note that here we divide variance by the number of trials; // this is because variance is a biased estimator. int range = (max - min + 1); float mean = (max + min) / 2; float variance = ((range * range - 1) / 12) / num_trials; float stddev = sqrt(variance); static const float prediction_intervals[] = { 0.68269f, // 1.0 0.86639f, // 1.5 0.95450f, // 2.0 0.98758f, // 2.5 0.99730f, // 3.0 }; //// Simple normality test using the 68-95-99.7% rule for (u32 i = 0; i != ARRLEN(prediction_intervals); i++) { float deviations = i / 2.f + 1.f; int lbound = myround(mean - deviations * stddev); int ubound = myround(mean + deviations * stddev); UASSERT(lbound >= min); UASSERT(ubound <= max); int accum = 0; for (int j = lbound; j != ubound; j++) accum += bins[j - min]; float actual = (float)accum / num_samples; UASSERT(fabs(actual - prediction_intervals[i]) < 0.02); } } const int TestRandom::expected_pseudorandom_results[256] = { 0x02fa, 0x60d5, 0x6c10, 0x606b, 0x098b, 0x5f1e, 0x4f56, 0x3fbd, 0x77af, 0x4fe9, 0x419a, 0x6fe1, 0x177b, 0x6858, 0x36f8, 0x6d83, 0x14fc, 0x2d62, 0x1077, 0x23e2, 0x041b, 0x7a7e, 0x5b52, 0x215d, 0x682b, 0x4716, 0x47e3, 0x08c0, 0x1952, 0x56ae, 0x146d, 0x4b4f, 0x239f, 0x3fd0, 0x6794, 0x7796, 0x7be2, 0x75b7, 0x5691, 0x28ee, 0x2656, 0x40c0, 0x133c, 0x63cd, 0x2aeb, 0x518f, 0x7dbc, 0x6ad8, 0x736e, 0x5b05, 0x160b, 0x589f, 0x6f64, 0x5edc, 0x092c, 0x0a39, 0x199e, 0x1927, 0x562b, 0x2689, 0x3ba3, 0x366f, 0x46da, 0x4e49, 0x0abb, 0x40a1, 0x3846, 0x40db, 0x7adb, 0x6ec1, 0x6efa, 0x01cc, 0x6335, 0x4352, 0x72fb, 0x4b2d, 0x509a, 0x257e, 0x2f7d, 0x5891, 0x2195, 0x6107, 0x5269, 0x56e3, 0x4849, 0x38f7, 0x2791, 0x04f2, 0x4e05, 0x78ff, 0x6bae, 0x50b3, 0x74ad, 0x31af, 0x531e, 0x7d56, 0x11c9, 0x0b5e, 0x405e, 0x1e15, 0x7f6a, 0x5bd3, 0x6649, 0x71b4, 0x3ec2, 0x6ab4, 0x520e, 0x6ad6, 0x287e, 0x10b8, 0x18f2, 0x7107, 0x46ea, 0x1d85, 0x25cc, 0x2689, 0x35c1, 0x3065, 0x6237, 0x3edd, 0x23d9, 0x6fb5, 0x37a1, 0x3211, 0x526a, 0x4b09, 0x23f1, 0x58cc, 0x2e42, 0x341f, 0x5e16, 0x3d1a, 0x5e8c, 0x7a82, 0x4635, 0x2bf8, 0x6577, 0x3603, 0x1daf, 0x539f, 0x2e91, 0x6bd8, 0x42d3, 0x7a93, 0x26e3, 0x5a91, 0x6c67, 0x1b66, 0x3ac7, 0x18bf, 0x20d8, 0x7153, 0x558d, 0x7262, 0x653d, 0x417d, 0x3ed3, 0x3117, 0x600d, 0x6d04, 0x719c, 0x3afd, 0x6ba5, 0x17c5, 0x4935, 0x346c, 0x5479, 0x6ff6, 0x1fcc, 0x1054, 0x3f14, 0x6266, 0x3acc, 0x3b77, 0x71d8, 0x478b, 0x20fa, 0x4e46, 0x7e77, 0x5554, 0x3652, 0x719c, 0x072b, 0x61ad, 0x399f, 0x621d, 0x1bba, 0x41d0, 0x7fdc, 0x3e6c, 0x6a2a, 0x5253, 0x094e, 0x0c10, 0x3f43, 0x73eb, 0x4c5f, 0x1f23, 0x12c9, 0x0902, 0x5238, 0x50c0, 0x1b77, 0x3ffd, 0x0124, 0x302a, 0x26b9, 0x3648, 0x30a6, 0x1abc, 0x3031, 0x4029, 0x6358, 0x6696, 0x74e8, 0x6142, 0x4284, 0x0c00, 0x7e50, 0x41e3, 0x3782, 0x79a5, 0x60fe, 0x2d15, 0x3ed2, 0x7f70, 0x2b27, 0x6366, 0x5100, 0x7c44, 0x3ee0, 0x4e76, 0x7d34, 0x3a60, 0x140e, 0x613d, 0x1193, 0x268d, 0x1e2f, 0x3123, 0x6d61, 0x4e0b, 0x51ce, 0x13bf, 0x58d4, 0x4f43, 0x05c6, 0x4d6a, 0x7eb5, 0x2921, 0x2c36, 0x1c89, 0x63b9, 0x1555, 0x1f41, 0x2d9f, }; const u32 TestRandom::expected_pcgrandom_results[256] = { 0x48c593f8, 0x054f59f5, 0x0d062dc1, 0x23852a23, 0x7fbbc97b, 0x1f9f141e, 0x364e6ed8, 0x995bba58, 0xc9307dc0, 0x73fb34c4, 0xcd8de88d, 0x52e8ce08, 0x1c4a78e4, 0x25c0882e, 0x8a82e2e0, 0xe3bc3311, 0xb8068d42, 0x73186110, 0x19988df4, 0x69bd970b, 0x7214728c, 0x0aee320c, 0x2a5a536c, 0xaf48d715, 0x00bce504, 0xd2b8f548, 0x520df366, 0x96d8fff5, 0xa1bb510b, 0x63477049, 0xb85990b7, 0x7e090689, 0x275fb468, 0x50206257, 0x8bab4f8a, 0x0d6823db, 0x63faeaac, 0x2d92deeb, 0x2ba78024, 0x0d30f631, 0x338923a0, 0xd07248d8, 0xa5db62d3, 0xddba8af6, 0x0ad454e9, 0x6f0fd13a, 0xbbfde2bf, 0x91188009, 0x966b394d, 0xbb9d2012, 0x7e6926cb, 0x95183860, 0x5ff4c59b, 0x035f628a, 0xb67085ef, 0x33867e23, 0x68d1b887, 0x2e3298d7, 0x84fd0650, 0x8bc91141, 0x6fcb0452, 0x2836fee9, 0x2e83c0a3, 0xf1bafdc5, 0x9ff77777, 0xfdfbba87, 0x527aebeb, 0x423e5248, 0xd1756490, 0xe41148fa, 0x3361f7b4, 0xa2824f23, 0xf4e08072, 0xc50442be, 0x35adcc21, 0x36be153c, 0xc7709012, 0xf0eeb9f2, 0x3d73114e, 0x1c1574ee, 0x92095b9c, 0x1503d01c, 0xd6ce0677, 0x026a8ec1,