dlls/ntdll/tests/rtlbitmap.c

   1 /* Unit test suite for Rtl bitmap functions
   2  *
   3  * Copyright 2002 Jon Griffiths
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18  *
  19  * NOTES
  20  * We use function pointers here as some of the bitmap functions exist only
  21  * in later versions of ntdll.
  22  */
  23
  24 #include "ntdll_test.h"
  25
  26 #ifdef __WINE_WINTERNL_H
  27
  28 /* Function ptrs for ordinal calls */
  29 static HMODULE hntdll = 0;
  30 static VOID (WINAPI *pRtlInitializeBitMap)(PRTL_BITMAP,LPBYTE,ULONG);
  31 static VOID (WINAPI *pRtlSetAllBits)(PRTL_BITMAP);
  32 static VOID (WINAPI *pRtlClearAllBits)(PRTL_BITMAP);
  33 static VOID (WINAPI *pRtlSetBits)(PRTL_BITMAP,ULONG,ULONG);
  34 static VOID (WINAPI *pRtlClearBits)(PRTL_BITMAP,ULONG,ULONG);
  35 static BOOLEAN (WINAPI *pRtlAreBitsSet)(PRTL_BITMAP,ULONG,ULONG);
  36 static BOOLEAN (WINAPI *pRtlAreBitsClear)(PRTL_BITMAP,ULONG,ULONG);
  37 static ULONG (WINAPI *pRtlFindSetBitsAndClear)(PRTL_BITMAP,ULONG,ULONG);
  38 static ULONG (WINAPI *pRtlFindClearBitsAndSet)(PRTL_BITMAP,ULONG,ULONG);
  39 static CCHAR (WINAPI *pRtlFindMostSignificantBit)(ULONGLONG);
  40 static CCHAR (WINAPI *pRtlFindLeastSignificantBit)(ULONGLONG);
  41 static ULONG (WINAPI *pRtlFindSetRuns)(PRTL_BITMAP,PRTL_BITMAP_RUN,ULONG,BOOLEAN);
  42 static ULONG (WINAPI *pRtlFindClearRuns)(PRTL_BITMAP,PRTL_BITMAP_RUN,ULONG,BOOLEAN);
  43 static ULONG (WINAPI *pRtlNumberOfSetBits)(PRTL_BITMAP);
  44 static ULONG (WINAPI *pRtlNumberOfClearBits)(PRTL_BITMAP);
  45 static ULONG (WINAPI *pRtlFindLongestRunSet)(PRTL_BITMAP,PULONG);
  46 static ULONG (WINAPI *pRtlFindLongestRunClear)(PRTL_BITMAP,PULONG);
  47
  48 static BYTE buff[256];
  49 static RTL_BITMAP bm;
  50
  51 static void InitFunctionPtrs()
  52 {
  53   hntdll = LoadLibraryA("ntdll.dll");
  54   ok(hntdll != 0, "LoadLibrary failed\n");
  55   if (hntdll)
  56   {
  57     pRtlInitializeBitMap = (void *)GetProcAddress(hntdll, "RtlInitializeBitMap");
  58     pRtlSetAllBits = (void *)GetProcAddress(hntdll, "RtlSetAllBits");
  59     pRtlClearAllBits = (void *)GetProcAddress(hntdll, "RtlClearAllBits");
  60     pRtlSetBits = (void *)GetProcAddress(hntdll, "RtlSetBits");
  61     pRtlClearBits = (void *)GetProcAddress(hntdll, "RtlClearBits");
  62     pRtlAreBitsSet = (void *)GetProcAddress(hntdll, "RtlAreBitsSet");
  63     pRtlAreBitsClear = (void *)GetProcAddress(hntdll, "RtlAreBitsClear");
  64     pRtlNumberOfSetBits = (void *)GetProcAddress(hntdll, "RtlNumberOfSetBits");
  65     pRtlNumberOfClearBits = (void *)GetProcAddress(hntdll, "RtlNumberOfClearBits");
  66     pRtlFindSetBitsAndClear = (void *)GetProcAddress(hntdll, "RtlFindSetBitsAndClear");
  67     pRtlFindClearBitsAndSet = (void *)GetProcAddress(hntdll, "RtlFindClearBitsAndSet");
  68     pRtlFindMostSignificantBit = (void *)GetProcAddress(hntdll, "RtlFindMostSignificantBit");
  69     pRtlFindLeastSignificantBit = (void *)GetProcAddress(hntdll, "RtlFindLeastSignificantBit");
  70     pRtlFindSetRuns = (void *)GetProcAddress(hntdll, "RtlFindSetRuns");
  71     pRtlFindClearRuns = (void *)GetProcAddress(hntdll, "RtlFindClearRuns");
  72     pRtlFindLongestRunSet = (void *)GetProcAddress(hntdll, "RtlFindLongestRunSet");
  73     pRtlFindLongestRunClear = (void *)GetProcAddress(hntdll, "RtlFindLongestRunClear");
  74   }
  75 }
  76
  77 static void test_RtlInitializeBitMap(void)
  78 {
  79   bm.SizeOfBitMap = 0;
  80   bm.Buffer = 0;
  81
  82   memset(buff, 0, sizeof(buff));
  83   buff[0] = 77; /* Check buffer is not written to during init */
  84   buff[79] = 77;
  85
  86   pRtlInitializeBitMap(&bm, buff, 800);
  87   ok(bm.SizeOfBitMap == 800, "size uninitialised\n");
  88   ok(bm.Buffer == (PULONG)buff,"buffer uninitialised\n");
  89   ok(buff[0] == 77 && buff[79] == 77, "wrote to buffer\n");
  90 }
  91
  92 static void test_RtlSetAllBits(void)
  93 {
  94   if (!pRtlSetAllBits)
  95     return;
  96
  97   memset(buff, 0 , sizeof(buff));
  98   pRtlInitializeBitMap(&bm, buff, 1);
  99
 100   pRtlSetAllBits(&bm);
 101   ok(buff[0] == 0xff && buff[1] == 0xff && buff[2] == 0xff &&
 102      buff[3] == 0xff, "didn't round up size\n");
 103   ok(buff[4] == 0, "set more than rounded size\n");
 104 }
 105
 106 static void test_RtlClearAllBits()
 107 {
 108   if (!pRtlClearAllBits)
 109     return;
 110
 111   memset(buff, 0xff , sizeof(buff));
 112   pRtlInitializeBitMap(&bm, buff, 1);
 113
 114   pRtlClearAllBits(&bm);
 115   ok(!buff[0] && !buff[1] && !buff[2] && !buff[3], "didn't round up size\n");
 116   ok(buff[4] == 0xff, "cleared more than rounded size\n");
 117 }
 118
 119 static void test_RtlSetBits()
 120 {
 121   if (!pRtlSetBits)
 122     return;
 123
 124   memset(buff, 0 , sizeof(buff));
 125   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 126
 127   pRtlSetBits(&bm, 0, 1);
 128   ok(buff[0] == 1, "didn't set 1st bit\n");
 129
 130   buff[0] = 0;
 131   pRtlSetBits(&bm, 7, 2);
 132   ok(buff[0] == 0x80 && buff[1] == 1, "didn't span w/len < 8\n");
 133
 134   buff[0] = buff[1] = 0;
 135   pRtlSetBits(&bm, 7, 10);
 136   ok(buff[0] == 0x80 && buff[1] == 0xff && buff[2] == 1, "didn't span w/len > 8\n");
 137
 138   buff[0] = buff[1] = buff[2] = 0;
 139   pRtlSetBits(&bm, 0, 8); /* 1st byte */
 140   ok(buff[0] == 0xff, "didn't set all bits\n");
 141   ok(!buff[1], "set too many bits\n");
 142
 143   pRtlSetBits(&bm, sizeof(buff)*8-1, 1); /* last bit */
 144   ok(buff[sizeof(buff)-1] == 0x80, "didn't set last bit\n");
 145 }
 146
 147 static void test_RtlClearBits()
 148 {
 149   if (!pRtlClearBits)
 150     return;
 151
 152   memset(buff, 0xff , sizeof(buff));
 153   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 154
 155   pRtlClearBits(&bm, 0, 1);
 156   ok(buff[0] == 0xfe, "didn't clear 1st bit\n");
 157
 158   buff[0] = 0xff;
 159   pRtlClearBits(&bm, 7, 2);
 160   ok(buff[0] == 0x7f && buff[1] == 0xfe, "didn't span w/len < 8\n");
 161
 162   buff[0] = buff[1] = 0xff;
 163   pRtlClearBits(&bm, 7, 10);
 164   ok(buff[0] == 0x7f && buff[1] == 0 && buff[2] == 0xfe, "didn't span w/len > 8\n");
 165
 166   buff[0] = buff[1] = buff[2] = 0xff;
 167   pRtlClearBits(&bm, 0, 8);  /* 1st byte */
 168   ok(!buff[0], "didn't clear all bits\n");
 169   ok(buff[1] == 0xff, "cleared too many bits\n");
 170
 171   pRtlClearBits(&bm, sizeof(buff)*8-1, 1);
 172   ok(buff[sizeof(buff)-1] == 0x7f, "didn't set last bit\n");
 173 }
 174
 175 static void test_RtlCheckBit()
 176 {
 177   BOOLEAN bRet;
 178
 179   memset(buff, 0 , sizeof(buff));
 180   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 181   pRtlSetBits(&bm, 0, 1);
 182   pRtlSetBits(&bm, 7, 2);
 183   pRtlSetBits(&bm, sizeof(buff)*8-1, 1);
 184
 185   bRet = RtlCheckBit(&bm, 0);
 186   ok (bRet, "didn't find set bit\n");
 187   bRet = RtlCheckBit(&bm, 7);
 188   ok (bRet, "didn't find set bit\n");
 189   bRet = RtlCheckBit(&bm, 8);
 190   ok (bRet, "didn't find set bit\n");
 191   bRet = RtlCheckBit(&bm, sizeof(buff)*8-1);
 192   ok (bRet, "didn't find set bit\n");
 193   bRet = RtlCheckBit(&bm, 1);
 194   ok (!bRet, "found non set bit\n");
 195   bRet = RtlCheckBit(&bm, sizeof(buff)*8-2);
 196   ok (!bRet, "found non set bit\n");
 197 }
 198
 199 static void test_RtlAreBitsSet()
 200 {
 201   BOOLEAN bRet;
 202
 203   if (!pRtlAreBitsSet)
 204     return;
 205
 206   memset(buff, 0 , sizeof(buff));
 207   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 208
 209   bRet = pRtlAreBitsSet(&bm, 0, 1);
 210   ok (!bRet, "found set bits after init\n");
 211
 212   pRtlSetBits(&bm, 0, 1);
 213   bRet = pRtlAreBitsSet(&bm, 0, 1);
 214   ok (bRet, "didn't find set bits\n");
 215
 216   buff[0] = 0;
 217   pRtlSetBits(&bm, 7, 2);
 218   bRet = pRtlAreBitsSet(&bm, 7, 2);
 219   ok(bRet, "didn't find w/len < 8\n");
 220   bRet = pRtlAreBitsSet(&bm, 6, 3);
 221   ok(!bRet, "found non set bit\n");
 222   bRet = pRtlAreBitsSet(&bm, 7, 3);
 223   ok(!bRet, "found non set bit\n");
 224
 225   buff[0] = buff[1] = 0;
 226   pRtlSetBits(&bm, 7, 10);
 227   bRet = pRtlAreBitsSet(&bm, 7, 10);
 228   ok(bRet, "didn't find w/len < 8\n");
 229   bRet = pRtlAreBitsSet(&bm, 6, 11);
 230   ok(!bRet, "found non set bit\n");
 231   bRet = pRtlAreBitsSet(&bm, 7, 11);
 232   ok(!bRet, "found non set bit\n");
 233
 234   buff[0] = buff[1] = buff[2] = 0;
 235   pRtlSetBits(&bm, 0, 8); /* 1st byte */
 236   bRet = pRtlAreBitsSet(&bm, 0, 8);
 237   ok(bRet, "didn't find whole byte\n");
 238
 239   pRtlSetBits(&bm, sizeof(buff)*8-1, 1);
 240   bRet = pRtlAreBitsSet(&bm, sizeof(buff)*8-1, 1);
 241   ok(bRet, "didn't find last bit\n");
 242 }
 243
 244 static void test_RtlAreBitsClear()
 245 {
 246   BOOLEAN bRet;
 247
 248   if (!pRtlAreBitsClear)
 249     return;
 250
 251   memset(buff, 0xff , sizeof(buff));
 252   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 253
 254   bRet = pRtlAreBitsClear(&bm, 0, 1);
 255   ok (!bRet, "found clear bits after init\n");
 256
 257   pRtlClearBits(&bm, 0, 1);
 258   bRet = pRtlAreBitsClear(&bm, 0, 1);
 259   ok (bRet, "didn't find set bits\n");
 260
 261   buff[0] = 0xff;
 262   pRtlClearBits(&bm, 7, 2);
 263   bRet = pRtlAreBitsClear(&bm, 7, 2);
 264   ok(bRet, "didn't find w/len < 8\n");
 265   bRet = pRtlAreBitsClear(&bm, 6, 3);
 266   ok(!bRet, "found non clear bit\n");
 267   bRet = pRtlAreBitsClear(&bm, 7, 3);
 268   ok(!bRet, "found non clear bit\n");
 269
 270   buff[0] = buff[1] = 0xff;
 271   pRtlClearBits(&bm, 7, 10);
 272   bRet = pRtlAreBitsClear(&bm, 7, 10);
 273   ok(bRet, "didn't find w/len < 8\n");
 274   bRet = pRtlAreBitsClear(&bm, 6, 11);
 275   ok(!bRet, "found non clear bit\n");
 276   bRet = pRtlAreBitsClear(&bm, 7, 11);
 277   ok(!bRet, "found non clear bit\n");
 278
 279   buff[0] = buff[1] = buff[2] = 0xff;
 280   pRtlClearBits(&bm, 0, 8); /* 1st byte */
 281   bRet = pRtlAreBitsClear(&bm, 0, 8);
 282   ok(bRet, "didn't find whole byte\n");
 283
 284   pRtlClearBits(&bm, sizeof(buff)*8-1, 1);
 285   bRet = pRtlAreBitsClear(&bm, sizeof(buff)*8-1, 1);
 286   ok(bRet, "didn't find last bit\n");
 287 }
 288
 289 static void test_RtlNumberOfSetBits()
 290 {
 291   ULONG ulCount;
 292
 293   if (!pRtlNumberOfSetBits)
 294     return;
 295
 296   memset(buff, 0 , sizeof(buff));
 297   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 298
 299   ulCount = pRtlNumberOfSetBits(&bm);
 300   ok(ulCount == 0, "set bits after init\n");
 301
 302   pRtlSetBits(&bm, 0, 1); /* Set 1st bit */
 303   ulCount = pRtlNumberOfSetBits(&bm);
 304   ok(ulCount == 1, "count wrong\n");
 305
 306   pRtlSetBits(&bm, 7, 8); /* 8 more, spanning bytes 1-2 */
 307   ulCount = pRtlNumberOfSetBits(&bm);
 308   ok(ulCount == 8+1, "count wrong\n");
 309
 310   pRtlSetBits(&bm, 17, 33); /* 33 more crossing ULONG boundary */
 311   ulCount = pRtlNumberOfSetBits(&bm);
 312   ok(ulCount == 8+1+33, "count wrong\n");
 313
 314   pRtlSetBits(&bm, sizeof(buff)*8-1, 1); /* Set last bit */
 315   ulCount = pRtlNumberOfSetBits(&bm);
 316   ok(ulCount == 8+1+33+1, "count wrong\n");
 317 }
 318
 319 static void test_RtlNumberOfClearBits()
 320 {
 321   ULONG ulCount;
 322
 323   if (!pRtlNumberOfClearBits)
 324     return;
 325
 326   memset(buff, 0xff , sizeof(buff));
 327   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 328
 329   ulCount = pRtlNumberOfClearBits(&bm);
 330   ok(ulCount == 0, "cleared bits after init\n");
 331
 332   pRtlClearBits(&bm, 0, 1); /* Set 1st bit */
 333   ulCount = pRtlNumberOfClearBits(&bm);
 334   ok(ulCount == 1, "count wrong\n");
 335
 336   pRtlClearBits(&bm, 7, 8); /* 8 more, spanning bytes 1-2 */
 337   ulCount = pRtlNumberOfClearBits(&bm);
 338   ok(ulCount == 8+1, "count wrong\n");
 339
 340   pRtlClearBits(&bm, 17, 33); /* 33 more crossing ULONG boundary */
 341   ulCount = pRtlNumberOfClearBits(&bm);
 342   ok(ulCount == 8+1+33, "count wrong\n");
 343
 344   pRtlClearBits(&bm, sizeof(buff)*8-1, 1); /* Set last bit */
 345   ulCount = pRtlNumberOfClearBits(&bm);
 346   ok(ulCount == 8+1+33+1, "count wrong\n");
 347 }
 348
 349 /* Note: this tests RtlFindSetBits also */
 350 static void test_RtlFindSetBitsAndClear()
 351 {
 352   BOOLEAN bRet;
 353   ULONG ulPos;
 354
 355   if (!pRtlFindSetBitsAndClear)
 356     return;
 357
 358   memset(buff, 0, sizeof(buff));
 359   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 360
 361   pRtlSetBits(&bm, 0, 32);
 362   ulPos = pRtlFindSetBitsAndClear(&bm, 32, 0);
 363   ok (ulPos == 0, "didn't find bits\n");
 364   if(ulPos == 0)
 365   {
 366     bRet = pRtlAreBitsClear(&bm, 0, 32);
 367     ok (bRet, "found but didn't clear\n");
 368   }
 369
 370   memset(buff, 0 , sizeof(buff));
 371   pRtlSetBits(&bm, 40, 77);
 372   ulPos = pRtlFindSetBitsAndClear(&bm, 77, 0);
 373   ok (ulPos == 40, "didn't find bits\n");
 374   if(ulPos == 40)
 375   {
 376     bRet = pRtlAreBitsClear(&bm, 40, 77);
 377     ok (bRet, "found but didn't clear\n");
 378   }
 379 }
 380
 381 /* Note: this tests RtlFindClearBits also */
 382 static void test_RtlFindClearBitsAndSet()
 383 {
 384   BOOLEAN bRet;
 385   ULONG ulPos;
 386
 387   if (!pRtlFindClearBitsAndSet)
 388     return;
 389
 390   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 391
 392   memset(buff, 0xff, sizeof(buff));
 393   pRtlSetBits(&bm, 0, 32);
 394   ulPos = pRtlFindSetBitsAndClear(&bm, 32, 0);
 395   ok (ulPos == 0, "didn't find bits\n");
 396   if(ulPos == 0)
 397   {
 398       bRet = pRtlAreBitsClear(&bm, 0, 32);
 399       ok (bRet, "found but didn't clear\n");
 400   }
 401
 402   memset(buff, 0xff , sizeof(buff));
 403   pRtlClearBits(&bm, 40, 77);
 404   ulPos = pRtlFindClearBitsAndSet(&bm, 77, 50);
 405   ok (ulPos == 40, "didn't find bits\n");
 406   if(ulPos == 40)
 407   {
 408     bRet = pRtlAreBitsSet(&bm, 40, 77);
 409     ok (bRet, "found but didn't set\n");
 410   }
 411 }
 412
 413 static void test_RtlFindMostSignificantBit()
 414 {
 415   int i;
 416   CCHAR cPos;
 417   ULONGLONG ulLong;
 418
 419   if (!pRtlFindMostSignificantBit)
 420     return;
 421
 422   for (i = 0; i < 64; i++)
 423   {
 424     ulLong = 1ul;
 425     ulLong <<= i;
 426
 427     cPos = pRtlFindMostSignificantBit(ulLong);
 428     ok (cPos == i, "didn't find MSB %llx %d %d\n", ulLong, i, cPos);
 429
 430     /* Set all bits lower than bit i */
 431     ulLong = ((ulLong - 1) << 1) | 1;
 432
 433     cPos = pRtlFindMostSignificantBit(ulLong);
 434     ok (cPos == i, "didn't find MSB %llx %d %d\n", ulLong, i, cPos);
 435   }
 436   cPos = pRtlFindMostSignificantBit(0);
 437   ok (cPos == -1, "found bit when not set\n");
 438 }
 439
 440 static void test_RtlFindLeastSignificantBit()
 441 {
 442   int i;
 443   CCHAR cPos;
 444   ULONGLONG ulLong;
 445
 446   if (!pRtlFindLeastSignificantBit)
 447     return;
 448
 449   for (i = 0; i < 64; i++)
 450   {
 451     ulLong = (ULONGLONG)1 << i;
 452
 453     cPos = pRtlFindLeastSignificantBit(ulLong);
 454     ok (cPos == i, "didn't find LSB %llx %d %d\n", ulLong, i, cPos);
 455
 456     ulLong = ~((ULONGLONG)0) << i;
 457
 458     cPos = pRtlFindLeastSignificantBit(ulLong);
 459     ok (cPos == i, "didn't find LSB %llx %d %d\n", ulLong, i, cPos);
 460   }
 461   cPos = pRtlFindLeastSignificantBit(0);
 462   ok (cPos == -1, "found bit when not set\n");
 463 }
 464
 465 /* Note: Also tests RtlFindLongestRunSet() */
 466 static void test_RtlFindSetRuns()
 467 {
 468   RTL_BITMAP_RUN runs[16];
 469   ULONG ulCount;
 470
 471   if (!pRtlFindSetRuns)
 472     return;
 473
 474   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 475
 476   memset(buff, 0, sizeof(buff));
 477   ulCount = pRtlFindSetRuns(&bm, runs, 16, TRUE);
 478   ok (ulCount == 0, "found set bits in empty bitmap\n");
 479
 480   memset(runs, 0, sizeof(runs));
 481   memset(buff, 0xff, sizeof(buff));
 482   ulCount = pRtlFindSetRuns(&bm, runs, 16, TRUE);
 483   ok (ulCount == 1, "didn't find set bits\n");
 484   ok (runs[0].StartingIndex == 0,"bad start\n");
 485   ok (runs[0].NumberOfBits == sizeof(buff)*8,"bad size\n");
 486
 487   /* Set up 3 runs */
 488   memset(runs, 0, sizeof(runs));
 489   memset(buff, 0, sizeof(buff));
 490   pRtlSetBits(&bm, 7, 19);
 491   pRtlSetBits(&bm, 101, 3);
 492   pRtlSetBits(&bm, 1877, 33);
 493
 494   /* Get first 2 */
 495   ulCount = pRtlFindSetRuns(&bm, runs, 2, FALSE);
 496   ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 101,"bad find\n");
 497   ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 101,"bad find\n");
 498   ok (runs[0].NumberOfBits + runs[1].NumberOfBits == 19 + 3,"bad size\n");
 499   ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
 500   ok (runs[2].StartingIndex == 0,"found extra run\n");
 501
 502   /* Get longest 3 */
 503   memset(runs, 0, sizeof(runs));
 504   ulCount = pRtlFindSetRuns(&bm, runs, 2, TRUE);
 505   ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 1877,"bad find\n");
 506   ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 1877,"bad find\n");
 507   ok (runs[0].NumberOfBits + runs[1].NumberOfBits == 33 + 19,"bad size\n");
 508   ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
 509   ok (runs[2].StartingIndex == 0,"found extra run\n");
 510
 511   /* Get all 3 */
 512   memset(runs, 0, sizeof(runs));
 513   ulCount = pRtlFindSetRuns(&bm, runs, 3, TRUE);
 514   ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 101 ||
 515       runs[0].StartingIndex == 1877,"bad find\n");
 516   ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 101 ||
 517       runs[1].StartingIndex == 1877,"bad find\n");
 518   ok (runs[2].StartingIndex == 7 || runs[2].StartingIndex == 101 ||
 519       runs[2].StartingIndex == 1877,"bad find\n");
 520   ok (runs[0].NumberOfBits + runs[1].NumberOfBits
 521       + runs[2].NumberOfBits == 19 + 3 + 33,"bad size\n");
 522   ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
 523   ok (runs[1].StartingIndex != runs[2].StartingIndex,"found run twice\n");
 524   ok (runs[3].StartingIndex == 0,"found extra run\n");
 525
 526   if (pRtlFindLongestRunSet)
 527   {
 528     ULONG ulStart = 0;
 529
 530     ulCount = pRtlFindLongestRunSet(&bm, &ulStart);
 531     ok(ulCount == 33 && ulStart == 1877,"didn't find longest %ld %ld\n",ulCount,ulStart);
 532
 533     memset(buff, 0, sizeof(buff));
 534     ulCount = pRtlFindLongestRunSet(&bm, &ulStart);
 535     ok(ulCount == 0,"found longest when none set\n");
 536   }
 537 }
 538
 539 /* Note: Also tests RtlFindLongestRunClear() */
 540 static void test_RtlFindClearRuns()
 541 {
 542   RTL_BITMAP_RUN runs[16];
 543   ULONG ulCount;
 544
 545   if (!pRtlFindClearRuns)
 546     return;
 547
 548   pRtlInitializeBitMap(&bm, buff, sizeof(buff)*8);
 549
 550   memset(buff, 0xff, sizeof(buff));
 551   ulCount = pRtlFindClearRuns(&bm, runs, 16, TRUE);
 552   ok (ulCount == 0, "found clear bits in full bitmap\n");
 553
 554   memset(runs, 0, sizeof(runs));
 555   memset(buff, 0, sizeof(buff));
 556   ulCount = pRtlFindClearRuns(&bm, runs, 16, TRUE);
 557   ok (ulCount == 1, "didn't find clear bits\n");
 558   ok (runs[0].StartingIndex == 0,"bad start\n");
 559   ok (runs[0].NumberOfBits == sizeof(buff)*8,"bad size\n");
 560
 561   /* Set up 3 runs */
 562   memset(runs, 0, sizeof(runs));
 563   memset(buff, 0xff, sizeof(buff));
 564   pRtlClearBits(&bm, 7, 19);
 565   pRtlClearBits(&bm, 101, 3);
 566   pRtlClearBits(&bm, 1877, 33);
 567
 568   /* Get first 2 */
 569   ulCount = pRtlFindClearRuns(&bm, runs, 2, FALSE);
 570   ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 101,"bad find\n");
 571   ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 101,"bad find\n");
 572   ok (runs[0].NumberOfBits + runs[1].NumberOfBits == 19 + 3,"bad size\n");
 573   ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
 574   ok (runs[2].StartingIndex == 0,"found extra run\n");
 575
 576   /* Get longest 3 */
 577   memset(runs, 0, sizeof(runs));
 578   ulCount = pRtlFindClearRuns(&bm, runs, 2, TRUE);
 579   ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 1877,"bad find\n");
 580   ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 1877,"bad find\n");
 581   ok (runs[0].NumberOfBits + runs[1].NumberOfBits == 33 + 19,"bad size\n");
 582   ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
 583   ok (runs[2].StartingIndex == 0,"found extra run\n");
 584
 585   /* Get all 3 */
 586   memset(runs, 0, sizeof(runs));
 587   ulCount = pRtlFindClearRuns(&bm, runs, 3, TRUE);
 588   ok (runs[0].StartingIndex == 7 || runs[0].StartingIndex == 101 ||
 589       runs[0].StartingIndex == 1877,"bad find\n");
 590   ok (runs[1].StartingIndex == 7 || runs[1].StartingIndex == 101 ||
 591       runs[1].StartingIndex == 1877,"bad find\n");
 592   ok (runs[2].StartingIndex == 7 || runs[2].StartingIndex == 101 ||
 593       runs[2].StartingIndex == 1877,"bad find\n");
 594   ok (runs[0].NumberOfBits + runs[1].NumberOfBits
 595       + runs[2].NumberOfBits == 19 + 3 + 33,"bad size\n");
 596   ok (runs[0].StartingIndex != runs[1].StartingIndex,"found run twice\n");
 597   ok (runs[1].StartingIndex != runs[2].StartingIndex,"found run twice\n");
 598   ok (runs[3].StartingIndex == 0,"found extra run\n");
 599
 600   if (pRtlFindLongestRunClear)
 601   {
 602     ULONG ulStart = 0;
 603
 604     ulCount = pRtlFindLongestRunClear(&bm, &ulStart);
 605     ok(ulCount == 33 && ulStart == 1877,"didn't find longest\n");
 606
 607     memset(buff, 0xff, sizeof(buff));
 608     ulCount = pRtlFindLongestRunClear(&bm, &ulStart);
 609     ok(ulCount == 0,"found longest when none clear\n");
 610   }
 611
 612 }
 613 #endif
 614
 615 START_TEST(rtlbitmap)
 616 {
 617 #ifdef __WINE_WINTERNL_H
 618   InitFunctionPtrs();
 619
 620   if (pRtlInitializeBitMap)
 621   {
 622     test_RtlInitializeBitMap();
 623     test_RtlSetAllBits();
 624     test_RtlClearAllBits();
 625     test_RtlSetBits();
 626     test_RtlClearBits();
 627     test_RtlCheckBit();
 628     test_RtlAreBitsSet();
 629     test_RtlAreBitsClear();
 630     test_RtlNumberOfSetBits();
 631     test_RtlNumberOfClearBits();
 632     test_RtlFindSetBitsAndClear();
 633     test_RtlFindClearBitsAndSet();
 634     test_RtlFindMostSignificantBit();
 635     test_RtlFindLeastSignificantBit();
 636     test_RtlFindSetRuns();
 637     test_RtlFindClearRuns();
 638   }
 639 #endif
 640 }