bit_array.c 81 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160
  1. /*
  2. bit_array.c
  3. project: bit array C library
  4. url: https://github.com/noporpoise/BitArray/
  5. maintainer: Isaac Turner <turner.isaac@gmail.com>
  6. license: Public Domain, no warranty
  7. date: Aug 2014
  8. */
  9. // 64 bit words
  10. // Array length can be zero
  11. // Unused top bits must be zero
  12. #include <stdlib.h>
  13. #include <stdarg.h>
  14. #include <stdio.h>
  15. #include <limits.h> // ULONG_MAX
  16. #include <errno.h>
  17. #include <signal.h> // needed for abort()
  18. #include <string.h> // memset()
  19. #include <assert.h>
  20. #include <time.h> // needed for seeding rand()
  21. #include <unistd.h> // need for getpid() for seeding rand number
  22. #include <ctype.h> // need for tolower()
  23. #include <errno.h> // perror()
  24. #include <sys/time.h> // for seeding random
  25. // Windows includes
  26. #if defined(_WIN32)
  27. #include <intrin.h>
  28. #endif
  29. #include "bit_array.h"
  30. #include "bit_macros.h"
  31. //
  32. // Tables of constants
  33. //
  34. // byte reverse look up table
  35. static const word_t reverse_table[256] =
  36. {
  37. 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
  38. 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
  39. 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
  40. 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
  41. 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,
  42. 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
  43. 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,
  44. 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
  45. 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,
  46. 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
  47. 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA,
  48. 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
  49. 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6,
  50. 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
  51. 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
  52. 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
  53. 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1,
  54. 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
  55. 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9,
  56. 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
  57. 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,
  58. 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
  59. 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED,
  60. 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
  61. 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3,
  62. 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
  63. 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
  64. 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
  65. 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,
  66. 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
  67. 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
  68. 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF,
  69. };
  70. // Morton table for interleaving bytes
  71. static const word_t morton_table0[256] =
  72. {
  73. 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
  74. 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
  75. 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
  76. 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
  77. 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
  78. 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
  79. 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
  80. 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
  81. 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
  82. 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
  83. 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
  84. 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
  85. 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
  86. 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
  87. 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
  88. 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
  89. 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
  90. 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
  91. 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
  92. 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
  93. 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
  94. 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
  95. 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
  96. 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
  97. 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
  98. 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
  99. 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
  100. 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
  101. 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
  102. 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
  103. 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
  104. 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555,
  105. };
  106. // Morton table for interleaving bytes, shifted left 1 bit
  107. static const word_t morton_table1[256] =
  108. {
  109. 0x0000, 0x0002, 0x0008, 0x000A, 0x0020, 0x0022, 0x0028, 0x002A,
  110. 0x0080, 0x0082, 0x0088, 0x008A, 0x00A0, 0x00A2, 0x00A8, 0x00AA,
  111. 0x0200, 0x0202, 0x0208, 0x020A, 0x0220, 0x0222, 0x0228, 0x022A,
  112. 0x0280, 0x0282, 0x0288, 0x028A, 0x02A0, 0x02A2, 0x02A8, 0x02AA,
  113. 0x0800, 0x0802, 0x0808, 0x080A, 0x0820, 0x0822, 0x0828, 0x082A,
  114. 0x0880, 0x0882, 0x0888, 0x088A, 0x08A0, 0x08A2, 0x08A8, 0x08AA,
  115. 0x0A00, 0x0A02, 0x0A08, 0x0A0A, 0x0A20, 0x0A22, 0x0A28, 0x0A2A,
  116. 0x0A80, 0x0A82, 0x0A88, 0x0A8A, 0x0AA0, 0x0AA2, 0x0AA8, 0x0AAA,
  117. 0x2000, 0x2002, 0x2008, 0x200A, 0x2020, 0x2022, 0x2028, 0x202A,
  118. 0x2080, 0x2082, 0x2088, 0x208A, 0x20A0, 0x20A2, 0x20A8, 0x20AA,
  119. 0x2200, 0x2202, 0x2208, 0x220A, 0x2220, 0x2222, 0x2228, 0x222A,
  120. 0x2280, 0x2282, 0x2288, 0x228A, 0x22A0, 0x22A2, 0x22A8, 0x22AA,
  121. 0x2800, 0x2802, 0x2808, 0x280A, 0x2820, 0x2822, 0x2828, 0x282A,
  122. 0x2880, 0x2882, 0x2888, 0x288A, 0x28A0, 0x28A2, 0x28A8, 0x28AA,
  123. 0x2A00, 0x2A02, 0x2A08, 0x2A0A, 0x2A20, 0x2A22, 0x2A28, 0x2A2A,
  124. 0x2A80, 0x2A82, 0x2A88, 0x2A8A, 0x2AA0, 0x2AA2, 0x2AA8, 0x2AAA,
  125. 0x8000, 0x8002, 0x8008, 0x800A, 0x8020, 0x8022, 0x8028, 0x802A,
  126. 0x8080, 0x8082, 0x8088, 0x808A, 0x80A0, 0x80A2, 0x80A8, 0x80AA,
  127. 0x8200, 0x8202, 0x8208, 0x820A, 0x8220, 0x8222, 0x8228, 0x822A,
  128. 0x8280, 0x8282, 0x8288, 0x828A, 0x82A0, 0x82A2, 0x82A8, 0x82AA,
  129. 0x8800, 0x8802, 0x8808, 0x880A, 0x8820, 0x8822, 0x8828, 0x882A,
  130. 0x8880, 0x8882, 0x8888, 0x888A, 0x88A0, 0x88A2, 0x88A8, 0x88AA,
  131. 0x8A00, 0x8A02, 0x8A08, 0x8A0A, 0x8A20, 0x8A22, 0x8A28, 0x8A2A,
  132. 0x8A80, 0x8A82, 0x8A88, 0x8A8A, 0x8AA0, 0x8AA2, 0x8AA8, 0x8AAA,
  133. 0xA000, 0xA002, 0xA008, 0xA00A, 0xA020, 0xA022, 0xA028, 0xA02A,
  134. 0xA080, 0xA082, 0xA088, 0xA08A, 0xA0A0, 0xA0A2, 0xA0A8, 0xA0AA,
  135. 0xA200, 0xA202, 0xA208, 0xA20A, 0xA220, 0xA222, 0xA228, 0xA22A,
  136. 0xA280, 0xA282, 0xA288, 0xA28A, 0xA2A0, 0xA2A2, 0xA2A8, 0xA2AA,
  137. 0xA800, 0xA802, 0xA808, 0xA80A, 0xA820, 0xA822, 0xA828, 0xA82A,
  138. 0xA880, 0xA882, 0xA888, 0xA88A, 0xA8A0, 0xA8A2, 0xA8A8, 0xA8AA,
  139. 0xAA00, 0xAA02, 0xAA08, 0xAA0A, 0xAA20, 0xAA22, 0xAA28, 0xAA2A,
  140. 0xAA80, 0xAA82, 0xAA88, 0xAA8A, 0xAAA0, 0xAAA2, 0xAAA8, 0xAAAA,
  141. };
  142. //
  143. // Macros
  144. //
  145. // WORD_SIZE is the number of bits per word
  146. // sizeof gives size in bytes (8 bits per byte)
  147. #define WORD_SIZE 64
  148. // #define WORD_SIZE (sizeof(word_t) * 8)
  149. // POPCOUNT is number of bits set
  150. #if defined(_WIN32)
  151. // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
  152. static word_t __inline windows_popcount(word_t w)
  153. {
  154. w = w - ((w >> 1) & (word_t)~(word_t)0/3);
  155. w = (w & (word_t)~(word_t)0/15*3) + ((w >> 2) & (word_t)~(word_t)0/15*3);
  156. w = (w + (w >> 4)) & (word_t)~(word_t)0/255*15;
  157. c = (word_t)(w * ((word_t)~(word_t)0/255)) >> (sizeof(word_t) - 1) * 8;
  158. }
  159. static word_t __inline windows_parity(word_t w)
  160. {
  161. w ^= w >> 1;
  162. w ^= w >> 2;
  163. w = (w & 0x1111111111111111UL) * 0x1111111111111111UL;
  164. return (w >> 60) & 1;
  165. }
  166. #define POPCOUNT(x) windows_popcountl(x)
  167. #define PARITY(x) windows_parity(x)
  168. #else
  169. #define POPCOUNT(x) (unsigned)__builtin_popcountll(x)
  170. #define PARITY(x) (unsigned)__builtin_parityll(x)
  171. #endif
  172. #define MIN(a, b) (((a) <= (b)) ? (a) : (b))
  173. #define MAX(a, b) (((a) >= (b)) ? (a) : (b))
  174. // Make this a power of two
  175. #define INIT_CAPACITY_WORDS 2
  176. // word of all 1s
  177. #define WORD_MAX (~(word_t)0)
  178. #define SET_REGION(arr,start,len) _set_region((arr),(start),(len),FILL_REGION)
  179. #define CLEAR_REGION(arr,start,len) _set_region((arr),(start),(len),ZERO_REGION)
  180. #define TOGGLE_REGION(arr,start,len) _set_region((arr),(start),(len),SWAP_REGION)
  181. // Have we initialised with srand() ?
  182. static char rand_initiated = 0;
  183. static void _seed_rand()
  184. {
  185. if(!rand_initiated)
  186. {
  187. // Initialise random number generator
  188. struct timeval time;
  189. gettimeofday(&time, NULL);
  190. srand((((time.tv_sec ^ getpid()) * 1000001) + time.tv_usec));
  191. rand_initiated = 1;
  192. }
  193. }
  194. //
  195. // Common internal functions
  196. //
  197. #define bits_in_top_word(nbits) ((nbits) ? bitset64_idx((nbits) - 1) + 1 : 0)
  198. // Mostly used for debugging
  199. static inline void _print_word(word_t word, FILE* out)
  200. {
  201. word_offset_t i;
  202. for(i = 0; i < WORD_SIZE; i++)
  203. {
  204. fprintf(out, "%c", ((word >> i) & (word_t)0x1) == 0 ? '0' : '1');
  205. }
  206. }
  207. // prints right to left
  208. static inline char* _word_to_str(word_t word, char str[WORD_SIZE+1])
  209. __attribute__((unused));
  210. static inline char* _word_to_str(word_t word, char str[WORD_SIZE+1])
  211. {
  212. word_offset_t i;
  213. for(i = 0; i < WORD_SIZE; i++)
  214. {
  215. str[WORD_SIZE-i-1] = ((word >> i) & (word_t)0x1) == 0 ? '0' : '1';
  216. }
  217. str[WORD_SIZE] = '\0';
  218. return str;
  219. }
  220. // Used in debugging
  221. #ifdef DEBUG
  222. #define DEBUG_PRINT(msg,...) printf("[%s:%i] "msg, __FILE__, __LINE__, ##__VA_ARGS__);
  223. #define DEBUG_VALIDATE(a) validate_bitarr((a), __FILE__, __LINE__)
  224. #else
  225. #define DEBUG_PRINT(msg,...)
  226. #define DEBUG_VALIDATE(a)
  227. #endif
  228. void validate_bitarr(BIT_ARRAY *arr, const char *file, int lineno)
  229. {
  230. // Check top word is masked
  231. word_addr_t tw = arr->num_of_words == 0 ? 0 : arr->num_of_words - 1;
  232. bit_index_t top_bits = bits_in_top_word(arr->num_of_bits);
  233. int err = 0;
  234. if(arr->words[tw] > bitmask64(top_bits))
  235. {
  236. _print_word(arr->words[tw], stderr);
  237. fprintf(stderr, "\n[%s:%i] Expected %i bits in top word[%i]\n",
  238. file, lineno, (int)top_bits, (int)tw);
  239. err = 1;
  240. }
  241. // Check num of words is correct
  242. word_addr_t num_words = roundup_bits2words64(arr->num_of_bits);
  243. if(num_words != arr->num_of_words)
  244. {
  245. fprintf(stderr, "\n[%s:%i] num of words wrong "
  246. "[bits: %i, word: %i, actual words: %i]\n", file, lineno,
  247. (int)arr->num_of_bits, (int)num_words, (int)arr->num_of_words);
  248. err = 1;
  249. }
  250. if(err) abort();
  251. }
  252. // Reverse a word
  253. static inline word_t _reverse_word(word_t word)
  254. {
  255. word_t reverse = (reverse_table[(word) & 0xff] << 56) |
  256. (reverse_table[(word >> 8) & 0xff] << 48) |
  257. (reverse_table[(word >> 16) & 0xff] << 40) |
  258. (reverse_table[(word >> 24) & 0xff] << 32) |
  259. (reverse_table[(word >> 32) & 0xff] << 24) |
  260. (reverse_table[(word >> 40) & 0xff] << 16) |
  261. (reverse_table[(word >> 48) & 0xff] << 8) |
  262. (reverse_table[(word >> 56) & 0xff]);
  263. return reverse;
  264. }
  265. static inline void _mask_top_word(BIT_ARRAY* bitarr)
  266. {
  267. // Mask top word
  268. word_addr_t num_of_words = MAX(1, bitarr->num_of_words);
  269. word_offset_t bits_active = bits_in_top_word(bitarr->num_of_bits);
  270. bitarr->words[num_of_words-1] &= bitmask64(bits_active);
  271. }
  272. //
  273. // Get and set words (internal use only -- no bounds checking)
  274. //
  275. static inline word_t _get_word(const BIT_ARRAY* bitarr, bit_index_t start)
  276. {
  277. word_addr_t word_index = bitset64_wrd(start);
  278. word_offset_t word_offset = bitset64_idx(start);
  279. word_t result = bitarr->words[word_index] >> word_offset;
  280. word_offset_t bits_taken = WORD_SIZE - word_offset;
  281. // word_offset is now the number of bits we need from the next word
  282. // Check the next word has at least some bits
  283. if(word_offset > 0 && start + bits_taken < bitarr->num_of_bits)
  284. {
  285. result |= bitarr->words[word_index+1] << (WORD_SIZE - word_offset);
  286. }
  287. return result;
  288. }
  289. // Set 64 bits from a particular start position
  290. // Doesn't extend bit array
  291. static inline void _set_word(BIT_ARRAY* bitarr, bit_index_t start, word_t word)
  292. {
  293. word_addr_t word_index = bitset64_wrd(start);
  294. word_offset_t word_offset = bitset64_idx(start);
  295. if(word_offset == 0)
  296. {
  297. bitarr->words[word_index] = word;
  298. }
  299. else
  300. {
  301. bitarr->words[word_index]
  302. = (word << word_offset) |
  303. (bitarr->words[word_index] & bitmask64(word_offset));
  304. if(word_index+1 < bitarr->num_of_words)
  305. {
  306. bitarr->words[word_index+1]
  307. = (word >> (WORD_SIZE - word_offset)) |
  308. (bitarr->words[word_index+1] & (WORD_MAX << word_offset));
  309. }
  310. }
  311. // Mask top word
  312. _mask_top_word(bitarr);
  313. DEBUG_VALIDATE(bitarr);
  314. }
  315. static inline void _set_byte(BIT_ARRAY *bitarr, bit_index_t start, uint8_t byte)
  316. {
  317. word_t w = _get_word(bitarr, start);
  318. _set_word(bitarr, start, (w & ~(word_t)0xff) | byte);
  319. }
  320. // 4 bits
  321. static inline void _set_nibble(BIT_ARRAY *bitarr, bit_index_t start,
  322. uint8_t nibble)
  323. {
  324. word_t w = _get_word(bitarr, start);
  325. _set_word(bitarr, start, (w & ~(word_t)0xf) | nibble);
  326. }
  327. // Wrap around
  328. static inline word_t _get_word_cyclic(const BIT_ARRAY* bitarr, bit_index_t start)
  329. {
  330. word_t word = _get_word(bitarr, start);
  331. bit_index_t bits_taken = bitarr->num_of_bits - start;
  332. if(bits_taken < WORD_SIZE)
  333. {
  334. word |= (bitarr->words[0] << bits_taken);
  335. if(bitarr->num_of_bits < (bit_index_t)WORD_SIZE)
  336. {
  337. // Mask word to prevent repetition of the same bits
  338. word = word & bitmask64(bitarr->num_of_bits);
  339. }
  340. }
  341. return word;
  342. }
  343. // Wrap around
  344. static inline void _set_word_cyclic(BIT_ARRAY* bitarr,
  345. bit_index_t start, word_t word)
  346. {
  347. _set_word(bitarr, start, word);
  348. bit_index_t bits_set = bitarr->num_of_bits - start;
  349. if(bits_set < WORD_SIZE && start > 0)
  350. {
  351. word >>= bits_set;
  352. // Prevent overwriting the bits we've just set
  353. // by setting 'start' as the upper bound for the number of bits to write
  354. word_offset_t bits_remaining = MIN(WORD_SIZE - bits_set, start);
  355. word_t mask = bitmask64(bits_remaining);
  356. bitarr->words[0] = bitmask_merge(word, bitarr->words[0], mask);
  357. }
  358. }
  359. //
  360. // Fill a region (internal use only)
  361. //
  362. // FillAction is fill with 0 or 1 or toggle
  363. typedef enum {ZERO_REGION, FILL_REGION, SWAP_REGION} FillAction;
  364. static inline void _set_region(BIT_ARRAY* bitarr, bit_index_t start,
  365. bit_index_t length, FillAction action)
  366. {
  367. if(length == 0) return;
  368. word_addr_t first_word = bitset64_wrd(start);
  369. word_addr_t last_word = bitset64_wrd(start+length-1);
  370. word_offset_t foffset = bitset64_idx(start);
  371. word_offset_t loffset = bitset64_idx(start+length-1);
  372. if(first_word == last_word)
  373. {
  374. word_t mask = bitmask64(length) << foffset;
  375. switch(action)
  376. {
  377. case ZERO_REGION: bitarr->words[first_word] &= ~mask; break;
  378. case FILL_REGION: bitarr->words[first_word] |= mask; break;
  379. case SWAP_REGION: bitarr->words[first_word] ^= mask; break;
  380. }
  381. }
  382. else
  383. {
  384. // Set first word
  385. switch(action)
  386. {
  387. case ZERO_REGION: bitarr->words[first_word] &= bitmask64(foffset); break;
  388. case FILL_REGION: bitarr->words[first_word] |= ~bitmask64(foffset); break;
  389. case SWAP_REGION: bitarr->words[first_word] ^= ~bitmask64(foffset); break;
  390. }
  391. word_addr_t i;
  392. // Set whole words
  393. switch(action)
  394. {
  395. case ZERO_REGION:
  396. for(i = first_word + 1; i < last_word; i++)
  397. bitarr->words[i] = (word_t)0;
  398. break;
  399. case FILL_REGION:
  400. for(i = first_word + 1; i < last_word; i++)
  401. bitarr->words[i] = WORD_MAX;
  402. break;
  403. case SWAP_REGION:
  404. for(i = first_word + 1; i < last_word; i++)
  405. bitarr->words[i] ^= WORD_MAX;
  406. break;
  407. }
  408. // Set last word
  409. switch(action)
  410. {
  411. case ZERO_REGION: bitarr->words[last_word] &= ~bitmask64(loffset+1); break;
  412. case FILL_REGION: bitarr->words[last_word] |= bitmask64(loffset+1); break;
  413. case SWAP_REGION: bitarr->words[last_word] ^= bitmask64(loffset+1); break;
  414. }
  415. }
  416. }
  417. //
  418. // Constructor
  419. //
  420. // If cannot allocate memory, set errno to ENOMEM, return NULL
  421. BIT_ARRAY* bit_array_alloc(BIT_ARRAY* bitarr, bit_index_t nbits)
  422. {
  423. bitarr->num_of_bits = nbits;
  424. bitarr->num_of_words = roundup_bits2words64(nbits);
  425. bitarr->capacity_in_words = MAX(8, roundup2pow(bitarr->num_of_words));
  426. bitarr->words = (word_t*)calloc(bitarr->capacity_in_words, sizeof(word_t));
  427. if(bitarr->words == NULL) {
  428. errno = ENOMEM;
  429. return NULL;
  430. }
  431. return bitarr;
  432. }
  433. void bit_array_dealloc(BIT_ARRAY* bitarr)
  434. {
  435. free(bitarr->words);
  436. memset(bitarr, 0, sizeof(BIT_ARRAY));
  437. }
  438. // If cannot allocate memory, set errno to ENOMEM, return NULL
  439. BIT_ARRAY* bit_array_create(bit_index_t nbits)
  440. {
  441. BIT_ARRAY* bitarr = (BIT_ARRAY*)malloc(sizeof(BIT_ARRAY));
  442. // error if could not allocate enough memory
  443. if(bitarr == NULL || bit_array_alloc(bitarr, nbits) == NULL)
  444. {
  445. if(bitarr != NULL) free(bitarr);
  446. errno = ENOMEM;
  447. return NULL;
  448. }
  449. DEBUG_PRINT("Creating BIT_ARRAY (bits: %lu; allocated words: %lu; "
  450. "using words: %lu; WORD_SIZE: %i)\n",
  451. (unsigned long)nbits, (unsigned long)bitarr->capacity_in_words,
  452. (unsigned long)roundup_bits2words64(nbits), (int)WORD_SIZE);
  453. DEBUG_VALIDATE(bitarr);
  454. return bitarr;
  455. }
  456. //
  457. // Destructor
  458. //
  459. void bit_array_free(BIT_ARRAY* bitarr)
  460. {
  461. if(bitarr->words != NULL)
  462. free(bitarr->words);
  463. free(bitarr);
  464. }
  465. bit_index_t bit_array_length(const BIT_ARRAY* bit_arr)
  466. {
  467. return bit_arr->num_of_bits;
  468. }
  469. // Change the size of a bit array. Enlarging an array will add zeros
  470. // to the end of it. Returns 1 on success, 0 on failure (e.g. not enough memory)
  471. char bit_array_resize(BIT_ARRAY* bitarr, bit_index_t new_num_of_bits)
  472. {
  473. word_addr_t old_num_of_words = bitarr->num_of_words;
  474. word_addr_t new_num_of_words = roundup_bits2words64(new_num_of_bits);
  475. bitarr->num_of_bits = new_num_of_bits;
  476. bitarr->num_of_words = new_num_of_words;
  477. DEBUG_PRINT("Resize: old_num_of_words: %i; new_num_of_words: %i capacity: %i\n",
  478. (int)old_num_of_words, (int)new_num_of_words,
  479. (int)bitarr->capacity_in_words);
  480. if(new_num_of_words > bitarr->capacity_in_words)
  481. {
  482. // Need to change the amount of memory used
  483. word_addr_t old_capacity_in_words = bitarr->capacity_in_words;
  484. size_t old_capacity_in_bytes = old_capacity_in_words * sizeof(word_t);
  485. bitarr->capacity_in_words = roundup2pow(new_num_of_words);
  486. bitarr->capacity_in_words = MAX(8, bitarr->capacity_in_words);
  487. size_t new_capacity_in_bytes = bitarr->capacity_in_words * sizeof(word_t);
  488. bitarr->words = (word_t*)realloc(bitarr->words, new_capacity_in_bytes);
  489. if(bitarr->words == NULL)
  490. {
  491. // error - could not allocate enough memory
  492. perror("resize realloc");
  493. errno = ENOMEM;
  494. return 0;
  495. }
  496. // Need to zero new memory
  497. size_t num_bytes_to_zero = new_capacity_in_bytes - old_capacity_in_bytes;
  498. memset(bitarr->words + old_capacity_in_words, 0, num_bytes_to_zero);
  499. DEBUG_PRINT("zeroing from word %i for %i bytes\n", (int)old_capacity_in_words,
  500. (int)num_bytes_to_zero);
  501. }
  502. else if(new_num_of_words < old_num_of_words)
  503. {
  504. // Shrunk -- need to zero old memory
  505. size_t num_bytes_to_zero = (old_num_of_words - new_num_of_words)*sizeof(word_t);
  506. memset(bitarr->words + new_num_of_words, 0, num_bytes_to_zero);
  507. }
  508. // Mask top word
  509. _mask_top_word(bitarr);
  510. DEBUG_VALIDATE(bitarr);
  511. return 1;
  512. }
  513. void bit_array_resize_critical(BIT_ARRAY* bitarr, bit_index_t num_of_bits)
  514. {
  515. bit_index_t old_num_of_bits = bitarr->num_of_bits;
  516. if(!bit_array_resize(bitarr, num_of_bits))
  517. {
  518. fprintf(stderr, "Ran out of memory resizing [%lu -> %lu]",
  519. (unsigned long)old_num_of_bits, (unsigned long)num_of_bits);
  520. abort();
  521. }
  522. }
  523. // If bitarr length < num_bits, resizes to num_bits
  524. char bit_array_ensure_size(BIT_ARRAY* bitarr, bit_index_t ensure_num_of_bits)
  525. {
  526. if(bitarr->num_of_bits < ensure_num_of_bits)
  527. {
  528. return bit_array_resize(bitarr, ensure_num_of_bits);
  529. }
  530. return 1;
  531. }
  532. void bit_array_ensure_size_critical(BIT_ARRAY* bitarr, bit_index_t num_of_bits)
  533. {
  534. if(num_of_bits > bitarr->num_of_bits)
  535. {
  536. bit_array_resize_critical(bitarr, num_of_bits);
  537. }
  538. }
  539. static inline
  540. void _bit_array_ensure_nwords(BIT_ARRAY* bitarr, word_addr_t nwords,
  541. const char *file, int lineno, const char *func)
  542. {
  543. size_t newmem, oldmem;
  544. if(bitarr->capacity_in_words < nwords) {
  545. oldmem = bitarr->capacity_in_words * sizeof(word_t);
  546. bitarr->capacity_in_words = roundup2pow(nwords);
  547. newmem = bitarr->capacity_in_words * sizeof(word_t);
  548. bitarr->words = (word_t*)realloc(bitarr->words, newmem);
  549. if(bitarr->words == NULL) {
  550. fprintf(stderr, "[%s:%i:%s()] Ran out of memory resizing [%zu -> %zu]",
  551. file, lineno, func, oldmem, newmem);
  552. abort();
  553. }
  554. DEBUG_PRINT("Ensure nwords realloc %zu -> %zu\n", oldmem, newmem);
  555. }
  556. }
  557. //
  558. // Get, set, clear, assign and toggle individual bits
  559. //
  560. // Get the value of a bit (returns 0 or 1)
  561. char bit_array_get_bit(const BIT_ARRAY* bitarr, bit_index_t b)
  562. {
  563. assert(b < bitarr->num_of_bits);
  564. return bit_array_get(bitarr, b);
  565. }
  566. // set a bit (to 1) at position b
  567. void bit_array_set_bit(BIT_ARRAY* bitarr, bit_index_t b)
  568. {
  569. assert(b < bitarr->num_of_bits);
  570. bit_array_set(bitarr,b);
  571. DEBUG_VALIDATE(bitarr);
  572. }
  573. // clear a bit (to 0) at position b
  574. void bit_array_clear_bit(BIT_ARRAY* bitarr, bit_index_t b)
  575. {
  576. assert(b < bitarr->num_of_bits);
  577. bit_array_clear(bitarr, b);
  578. DEBUG_VALIDATE(bitarr);
  579. }
  580. // If bit is 0 -> 1, if bit is 1 -> 0. AKA 'flip'
  581. void bit_array_toggle_bit(BIT_ARRAY* bitarr, bit_index_t b)
  582. {
  583. assert(b < bitarr->num_of_bits);
  584. bit_array_toggle(bitarr, b);
  585. DEBUG_VALIDATE(bitarr);
  586. }
  587. // If char c != 0, set bit; otherwise clear bit
  588. void bit_array_assign_bit(BIT_ARRAY* bitarr, bit_index_t b, char c)
  589. {
  590. assert(b < bitarr->num_of_bits);
  591. bit_array_assign(bitarr, b, c ? 1 : 0);
  592. DEBUG_VALIDATE(bitarr);
  593. }
  594. //
  595. // Get, set etc with resize
  596. //
  597. // Get the value of a bit (returns 0 or 1)
  598. char bit_array_rget(BIT_ARRAY* bitarr, bit_index_t b)
  599. {
  600. bit_array_ensure_size_critical(bitarr, b+1);
  601. return bit_array_get(bitarr, b);
  602. }
  603. // set a bit (to 1) at position b
  604. void bit_array_rset(BIT_ARRAY* bitarr, bit_index_t b)
  605. {
  606. bit_array_ensure_size_critical(bitarr, b+1);
  607. bit_array_set(bitarr,b);
  608. DEBUG_VALIDATE(bitarr);
  609. }
  610. // clear a bit (to 0) at position b
  611. void bit_array_rclear(BIT_ARRAY* bitarr, bit_index_t b)
  612. {
  613. bit_array_ensure_size_critical(bitarr, b+1);
  614. bit_array_clear(bitarr, b);
  615. DEBUG_VALIDATE(bitarr);
  616. }
  617. // If bit is 0 -> 1, if bit is 1 -> 0. AKA 'flip'
  618. void bit_array_rtoggle(BIT_ARRAY* bitarr, bit_index_t b)
  619. {
  620. bit_array_ensure_size_critical(bitarr, b+1);
  621. bit_array_toggle(bitarr, b);
  622. DEBUG_VALIDATE(bitarr);
  623. }
  624. // If char c != 0, set bit; otherwise clear bit
  625. void bit_array_rassign(BIT_ARRAY* bitarr, bit_index_t b, char c)
  626. {
  627. bit_array_ensure_size_critical(bitarr, b+1);
  628. bit_array_assign(bitarr, b, c ? 1 : 0);
  629. DEBUG_VALIDATE(bitarr);
  630. }
  631. //
  632. // Set, clear and toggle several bits at once
  633. //
  634. // Set multiple bits at once.
  635. // e.g. set bits 1, 20 & 31: bit_array_set_bits(bitarr, 3, 1,20,31);
  636. void bit_array_set_bits(BIT_ARRAY* bitarr, size_t n, ...)
  637. {
  638. size_t i;
  639. va_list argptr;
  640. va_start(argptr, n);
  641. for(i = 0; i < n; i++)
  642. {
  643. unsigned int bit_index = va_arg(argptr, unsigned int);
  644. bit_array_set_bit(bitarr, bit_index);
  645. }
  646. va_end(argptr);
  647. DEBUG_VALIDATE(bitarr);
  648. }
  649. // Clear multiple bits at once.
  650. // e.g. clear bits 1, 20 & 31: bit_array_clear_bits(bitarr, 3, 1,20,31);
  651. void bit_array_clear_bits(BIT_ARRAY* bitarr, size_t n, ...)
  652. {
  653. size_t i;
  654. va_list argptr;
  655. va_start(argptr, n);
  656. for(i = 0; i < n; i++)
  657. {
  658. unsigned int bit_index = va_arg(argptr, unsigned int);
  659. bit_array_clear_bit(bitarr, bit_index);
  660. }
  661. va_end(argptr);
  662. DEBUG_VALIDATE(bitarr);
  663. }
  664. // Toggle multiple bits at once
  665. // e.g. toggle bits 1, 20 & 31: bit_array_toggle_bits(bitarr, 3, 1,20,31);
  666. void bit_array_toggle_bits(BIT_ARRAY* bitarr, size_t n, ...)
  667. {
  668. size_t i;
  669. va_list argptr;
  670. va_start(argptr, n);
  671. for(i = 0; i < n; i++)
  672. {
  673. unsigned int bit_index = va_arg(argptr, unsigned int);
  674. bit_array_toggle_bit(bitarr, bit_index);
  675. }
  676. va_end(argptr);
  677. DEBUG_VALIDATE(bitarr);
  678. }
  679. //
  680. // Set, clear and toggle all bits in a region
  681. //
  682. // Set all the bits in a region
  683. void bit_array_set_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len)
  684. {
  685. assert(start + len <= bitarr->num_of_bits);
  686. SET_REGION(bitarr, start, len);
  687. DEBUG_VALIDATE(bitarr);
  688. }
  689. // Clear all the bits in a region
  690. void bit_array_clear_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len)
  691. {
  692. assert(start + len <= bitarr->num_of_bits);
  693. CLEAR_REGION(bitarr, start, len);
  694. DEBUG_VALIDATE(bitarr);
  695. }
  696. // Toggle all the bits in a region
  697. void bit_array_toggle_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len)
  698. {
  699. assert(start + len <= bitarr->num_of_bits);
  700. TOGGLE_REGION(bitarr, start, len);
  701. DEBUG_VALIDATE(bitarr);
  702. }
  703. //
  704. // Set, clear and toggle all bits at once
  705. //
  706. // set all elements of data to one
  707. void bit_array_set_all(BIT_ARRAY* bitarr)
  708. {
  709. bit_index_t num_of_bytes = bitarr->num_of_words * sizeof(word_t);
  710. memset(bitarr->words, 0xFF, num_of_bytes);
  711. _mask_top_word(bitarr);
  712. DEBUG_VALIDATE(bitarr);
  713. }
  714. // set all elements of data to zero
  715. void bit_array_clear_all(BIT_ARRAY* bitarr)
  716. {
  717. memset(bitarr->words, 0, bitarr->num_of_words * sizeof(word_t));
  718. DEBUG_VALIDATE(bitarr);
  719. }
  720. // Set all 1 bits to 0, and all 0 bits to 1. AKA flip
  721. void bit_array_toggle_all(BIT_ARRAY* bitarr)
  722. {
  723. word_addr_t i;
  724. for(i = 0; i < bitarr->num_of_words; i++)
  725. {
  726. bitarr->words[i] ^= WORD_MAX;
  727. }
  728. _mask_top_word(bitarr);
  729. DEBUG_VALIDATE(bitarr);
  730. }
  731. //
  732. // Get a word at a time
  733. //
  734. uint64_t bit_array_get_word64(const BIT_ARRAY* bitarr, bit_index_t start)
  735. {
  736. assert(start < bitarr->num_of_bits);
  737. return (uint64_t)_get_word(bitarr, start);
  738. }
  739. uint32_t bit_array_get_word32(const BIT_ARRAY* bitarr, bit_index_t start)
  740. {
  741. assert(start < bitarr->num_of_bits);
  742. return (uint32_t)_get_word(bitarr, start);
  743. }
  744. uint16_t bit_array_get_word16(const BIT_ARRAY* bitarr, bit_index_t start)
  745. {
  746. assert(start < bitarr->num_of_bits);
  747. return (uint16_t)_get_word(bitarr, start);
  748. }
  749. uint8_t bit_array_get_word8(const BIT_ARRAY* bitarr, bit_index_t start)
  750. {
  751. assert(start < bitarr->num_of_bits);
  752. return (uint8_t)_get_word(bitarr, start);
  753. }
  754. uint64_t bit_array_get_wordn(const BIT_ARRAY* bitarr, bit_index_t start, int n)
  755. {
  756. assert(start < bitarr->num_of_bits);
  757. assert(n <= 64);
  758. return (uint64_t)(_get_word(bitarr, start) & bitmask64(n));
  759. }
  760. //
  761. // Set a word at a time
  762. //
  763. void bit_array_set_word64(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word)
  764. {
  765. assert(start < bitarr->num_of_bits);
  766. _set_word(bitarr, start, (word_t)word);
  767. }
  768. void bit_array_set_word32(BIT_ARRAY* bitarr, bit_index_t start, uint32_t word)
  769. {
  770. assert(start < bitarr->num_of_bits);
  771. word_t w = _get_word(bitarr, start);
  772. _set_word(bitarr, start, (w & ~(word_t)0xffffffff) | word);
  773. }
  774. void bit_array_set_word16(BIT_ARRAY* bitarr, bit_index_t start, uint16_t word)
  775. {
  776. assert(start < bitarr->num_of_bits);
  777. word_t w = _get_word(bitarr, start);
  778. _set_word(bitarr, start, (w & ~(word_t)0xffff) | word);
  779. }
  780. void bit_array_set_word8(BIT_ARRAY* bitarr, bit_index_t start, uint8_t byte)
  781. {
  782. assert(start < bitarr->num_of_bits);
  783. _set_byte(bitarr, start, byte);
  784. }
  785. void bit_array_set_wordn(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word, int n)
  786. {
  787. assert(start < bitarr->num_of_bits);
  788. assert(n <= 64);
  789. word_t w = _get_word(bitarr, start), m = bitmask64(n);
  790. _set_word(bitarr, start, bitmask_merge(word,w,m));
  791. }
  792. //
  793. // Number of bits set
  794. //
  795. // Get the number of bits set (hamming weight)
  796. bit_index_t bit_array_num_bits_set(const BIT_ARRAY* bitarr)
  797. {
  798. word_addr_t i;
  799. bit_index_t num_of_bits_set = 0;
  800. for(i = 0; i < bitarr->num_of_words; i++)
  801. {
  802. if(bitarr->words[i] > 0)
  803. {
  804. num_of_bits_set += POPCOUNT(bitarr->words[i]);
  805. }
  806. }
  807. return num_of_bits_set;
  808. }
  809. // Get the number of bits not set (1 - hamming weight)
  810. bit_index_t bit_array_num_bits_cleared(const BIT_ARRAY* bitarr)
  811. {
  812. return bitarr->num_of_bits - bit_array_num_bits_set(bitarr);
  813. }
  814. // Get the number of bits set in on array and not the other. This is equivalent
  815. // to hamming weight of the XOR when the two arrays are the same length.
  816. // e.g. 10101 vs 00111 => hamming distance 2 (XOR is 10010)
  817. bit_index_t bit_array_hamming_distance(const BIT_ARRAY* arr1,
  818. const BIT_ARRAY* arr2)
  819. {
  820. word_addr_t min_words = MIN(arr1->num_of_words, arr2->num_of_words);
  821. word_addr_t max_words = MAX(arr1->num_of_words, arr2->num_of_words);
  822. bit_index_t hamming_distance = 0;
  823. word_addr_t i;
  824. for(i = 0; i < min_words; i++)
  825. {
  826. hamming_distance += POPCOUNT(arr1->words[i] ^ arr2->words[i]);
  827. }
  828. if(min_words != max_words)
  829. {
  830. const BIT_ARRAY* long_arr
  831. = (arr1->num_of_words > arr2->num_of_words ? arr1 : arr2);
  832. for(i = min_words; i < max_words; i++)
  833. {
  834. hamming_distance += POPCOUNT(long_arr->words[i]);
  835. }
  836. }
  837. return hamming_distance;
  838. }
  839. // Parity - returns 1 if odd number of bits set, 0 if even
  840. char bit_array_parity(const BIT_ARRAY* bitarr)
  841. {
  842. word_addr_t w;
  843. unsigned int parity = 0;
  844. for(w = 0; w < bitarr->num_of_words; w++)
  845. {
  846. parity ^= PARITY(bitarr->words[w]);
  847. }
  848. return (char)parity;
  849. }
  850. //
  851. // Find indices of set/clear bits
  852. //
  853. // Find the index of the next bit that is set/clear, at or after `offset`
  854. // Returns 1 if such a bit is found, otherwise 0
  855. // Index is stored in the integer pointed to by `result`
  856. // If no such bit is found, value at `result` is not changed
  857. #define _next_bit_func_def(FUNC,GET) \
  858. char FUNC(const BIT_ARRAY* bitarr, bit_index_t offset, bit_index_t* result) \
  859. { \
  860. assert(offset < bitarr->num_of_bits); \
  861. if(bitarr->num_of_bits == 0 || offset >= bitarr->num_of_bits) { return 0; } \
  862. \
  863. /* Find first word that is greater than zero */ \
  864. word_addr_t i = bitset64_wrd(offset); \
  865. word_t w = GET(bitarr->words[i]) & ~bitmask64(bitset64_idx(offset)); \
  866. \
  867. while(1) { \
  868. if(w > 0) { \
  869. bit_index_t pos = i * WORD_SIZE + trailing_zeros(w); \
  870. if(pos < bitarr->num_of_bits) { *result = pos; return 1; } \
  871. else { return 0; } \
  872. } \
  873. i++; \
  874. if(i >= bitarr->num_of_words) break; \
  875. w = GET(bitarr->words[i]); \
  876. } \
  877. \
  878. return 0; \
  879. }
  880. // Find the index of the previous bit that is set/clear, before `offset`.
  881. // Returns 1 if such a bit is found, otherwise 0
  882. // Index is stored in the integer pointed to by `result`
  883. // If no such bit is found, value at `result` is not changed
  884. #define _prev_bit_func_def(FUNC,GET) \
  885. char FUNC(const BIT_ARRAY* bitarr, bit_index_t offset, bit_index_t* result) \
  886. { \
  887. assert(offset <= bitarr->num_of_bits); \
  888. if(bitarr->num_of_bits == 0 || offset == 0) { return 0; } \
  889. \
  890. /* Find prev word that is greater than zero */ \
  891. word_addr_t i = bitset64_wrd(offset-1); \
  892. word_t w = GET(bitarr->words[i]) & bitmask64(bitset64_idx(offset-1)+1); \
  893. \
  894. if(w > 0) { *result = (i+1) * WORD_SIZE - leading_zeros(w) - 1; return 1; } \
  895. \
  896. /* i is unsigned so have to use break when i == 0 */ \
  897. for(--i; i != BIT_INDEX_MAX; i--) { \
  898. w = GET(bitarr->words[i]); \
  899. if(w > 0) { \
  900. *result = (i+1) * WORD_SIZE - leading_zeros(w) - 1; \
  901. return 1; \
  902. } \
  903. } \
  904. \
  905. return 0; \
  906. }
  907. #define GET_WORD(x) (x)
  908. #define NEG_WORD(x) (~(x))
  909. _next_bit_func_def(bit_array_find_next_set_bit, GET_WORD);
  910. _next_bit_func_def(bit_array_find_next_clear_bit,NEG_WORD);
  911. _prev_bit_func_def(bit_array_find_prev_set_bit, GET_WORD);
  912. _prev_bit_func_def(bit_array_find_prev_clear_bit,NEG_WORD);
  913. // Find the index of the first bit that is set.
  914. // Returns 1 if a bit is set, otherwise 0
  915. // Index of first set bit is stored in the integer pointed to by result
  916. // If no bits are set, value at `result` is not changed
  917. char bit_array_find_first_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
  918. {
  919. return bit_array_find_next_set_bit(bitarr, 0, result);
  920. }
  921. // same same
  922. char bit_array_find_first_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
  923. {
  924. return bit_array_find_next_clear_bit(bitarr, 0, result);
  925. }
  926. // Find the index of the last bit that is set.
  927. // Returns 1 if a bit is set, otherwise 0
  928. // Index of last set bit is stored in the integer pointed to by `result`
  929. // If no bits are set, value at `result` is not changed
  930. char bit_array_find_last_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
  931. {
  932. return bit_array_find_prev_set_bit(bitarr, bitarr->num_of_bits, result);
  933. }
  934. // same same
  935. char bit_array_find_last_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
  936. {
  937. return bit_array_find_prev_clear_bit(bitarr, bitarr->num_of_bits, result);
  938. }
  939. //
  940. // "Sorting" bits
  941. //
  942. // Put all the 0s before all the 1s
  943. void bit_array_sort_bits(BIT_ARRAY* bitarr)
  944. {
  945. bit_index_t num_of_bits_set = bit_array_num_bits_set(bitarr);
  946. bit_index_t num_of_bits_cleared = bitarr->num_of_bits - num_of_bits_set;
  947. bit_array_set_all(bitarr);
  948. CLEAR_REGION(bitarr, 0, num_of_bits_cleared);
  949. DEBUG_VALIDATE(bitarr);
  950. }
  951. // Put all the 1s before all the 0s
  952. void bit_array_sort_bits_rev(BIT_ARRAY* bitarr)
  953. {
  954. bit_index_t num_of_bits_set = bit_array_num_bits_set(bitarr);
  955. bit_array_clear_all(bitarr);
  956. SET_REGION(bitarr, 0, num_of_bits_set);
  957. DEBUG_VALIDATE(bitarr);
  958. }
  959. //
  960. // Strings and printing
  961. //
  962. // Construct a BIT_ARRAY from a substring with given on and off characters.
  963. void bit_array_from_substr(BIT_ARRAY* bitarr, bit_index_t offset,
  964. const char *str, size_t len,
  965. const char *on, const char *off,
  966. char left_to_right)
  967. {
  968. bit_array_ensure_size(bitarr, offset + len);
  969. bit_array_clear_region(bitarr, offset, len);
  970. // BitArray region is now all 0s -- just set the 1s
  971. size_t i;
  972. bit_index_t j;
  973. for(i = 0; i < len; i++)
  974. {
  975. if(strchr(on, str[i]) != NULL)
  976. {
  977. j = offset + (left_to_right ? i : len - i - 1);
  978. bit_array_set(bitarr, j);
  979. }
  980. else { assert(strchr(off, str[i]) != NULL); }
  981. }
  982. DEBUG_VALIDATE(bitarr);
  983. }
  984. // From string method
  985. void bit_array_from_str(BIT_ARRAY* bitarr, const char* str)
  986. {
  987. bit_array_from_substr(bitarr, 0, str, strlen(str), "1", "0", 1);
  988. }
  989. // Takes a char array to write to. `str` must be bitarr->num_of_bits+1 in length
  990. // Terminates string with '\0'
  991. char* bit_array_to_str(const BIT_ARRAY* bitarr, char* str)
  992. {
  993. bit_index_t i;
  994. for(i = 0; i < bitarr->num_of_bits; i++)
  995. {
  996. str[i] = bit_array_get(bitarr, i) ? '1' : '0';
  997. }
  998. str[bitarr->num_of_bits] = '\0';
  999. return str;
  1000. }
  1001. char* bit_array_to_str_rev(const BIT_ARRAY* bitarr, char* str)
  1002. {
  1003. bit_index_t i;
  1004. for(i = 0; i < bitarr->num_of_bits; i++)
  1005. {
  1006. str[i] = bit_array_get(bitarr, bitarr->num_of_bits-i-1) ? '1' : '0';
  1007. }
  1008. str[bitarr->num_of_bits] = '\0';
  1009. return str;
  1010. }
  1011. // Get a string representations for a given region, using given on/off characters.
  1012. // Note: does not null-terminate
  1013. void bit_array_to_substr(const BIT_ARRAY* bitarr,
  1014. bit_index_t start, bit_index_t length,
  1015. char* str, char on, char off,
  1016. char left_to_right)
  1017. {
  1018. assert(start + length <= bitarr->num_of_bits);
  1019. bit_index_t i, j;
  1020. bit_index_t end = start + length - 1;
  1021. for(i = 0; i < length; i++)
  1022. {
  1023. j = (left_to_right ? start + i : end - i);
  1024. str[i] = bit_array_get(bitarr, j) ? on : off;
  1025. }
  1026. // str[length] = '\0';
  1027. }
  1028. // Print this array to a file stream. Prints '0's and '1'. Doesn't print newline.
  1029. void bit_array_print(const BIT_ARRAY* bitarr, FILE* fout)
  1030. {
  1031. bit_index_t i;
  1032. for(i = 0; i < bitarr->num_of_bits; i++)
  1033. {
  1034. fprintf(fout, "%c", bit_array_get(bitarr, i) ? '1' : '0');
  1035. }
  1036. }
  1037. // Print a string representations for a given region, using given on/off characters.
  1038. void bit_array_print_substr(const BIT_ARRAY* bitarr,
  1039. bit_index_t start, bit_index_t length,
  1040. FILE* fout, char on, char off,
  1041. char left_to_right)
  1042. {
  1043. assert(start + length <= bitarr->num_of_bits);
  1044. bit_index_t i, j;
  1045. bit_index_t end = start + length - 1;
  1046. for(i = 0; i < length; i++)
  1047. {
  1048. j = (left_to_right ? start + i : end - i);
  1049. fprintf(fout, "%c", bit_array_get(bitarr, j) ? on : off);
  1050. }
  1051. }
  1052. //
  1053. // Decimal
  1054. //
  1055. // Get bit array as decimal str (e.g. 0b1101 -> "13")
  1056. // len is the length of str char array -- will write at most len-1 chars
  1057. // returns the number of characters needed
  1058. // return is the same as strlen(str)
  1059. size_t bit_array_to_decimal(const BIT_ARRAY *bitarr, char *str, size_t len)
  1060. {
  1061. size_t i = 0;
  1062. if(bit_array_cmp_uint64(bitarr, 0) == 0)
  1063. {
  1064. if(len >= 2)
  1065. {
  1066. *str = '0';
  1067. *(str+1) = '\0';
  1068. }
  1069. return 1;
  1070. }
  1071. BIT_ARRAY *tmp = bit_array_clone(bitarr);
  1072. uint64_t rem;
  1073. str[len-1] = '\0';
  1074. while(bit_array_cmp_uint64(tmp, 0) != 0)
  1075. {
  1076. bit_array_div_uint64(tmp, 10, &rem);
  1077. if(i < len-1)
  1078. {
  1079. str[len-2-i] = '0' + rem;
  1080. }
  1081. i++;
  1082. }
  1083. if(i < len-1)
  1084. {
  1085. // Moves null-terminator as well
  1086. memmove(str, str+len-i-1, i+1);
  1087. }
  1088. bit_array_free(tmp);
  1089. return i;
  1090. }
  1091. // Get bit array from decimal str (e.g. "13" -> 0b1101)
  1092. // Returns number of characters used
  1093. size_t bit_array_from_decimal(BIT_ARRAY *bitarr, const char* decimal)
  1094. {
  1095. bit_array_clear_all(bitarr);
  1096. size_t i = 0;
  1097. if(decimal[0] == '\0' || decimal[0] < '0' || decimal[0] > '9')
  1098. {
  1099. return 0;
  1100. }
  1101. bit_array_add_uint64(bitarr, decimal[i] - '0');
  1102. i++;
  1103. while(decimal[i] != '\0' && decimal[i] >= '0' && decimal[i] <= '9')
  1104. {
  1105. bit_array_mul_uint64(bitarr, 10);
  1106. bit_array_add_uint64(bitarr, decimal[i] - '0');
  1107. i++;
  1108. }
  1109. return i;
  1110. }
  1111. //
  1112. // Hexidecimal
  1113. //
  1114. char bit_array_hex_to_nibble(char c, uint8_t *b)
  1115. {
  1116. c = tolower(c);
  1117. if(c >= '0' && c <= '9')
  1118. {
  1119. *b = c - '0';
  1120. return 1;
  1121. }
  1122. else if(c >= 'a' && c <= 'f')
  1123. {
  1124. *b = 0xa + (c - 'a');
  1125. return 1;
  1126. }
  1127. else
  1128. {
  1129. return 0;
  1130. }
  1131. }
  1132. char bit_array_nibble_to_hex(uint8_t b, char uppercase)
  1133. {
  1134. if(b <= 9)
  1135. {
  1136. return '0' + b;
  1137. }
  1138. else
  1139. {
  1140. return (uppercase ? 'A' : 'a') + (b - 0xa);
  1141. }
  1142. }
  1143. // Loads array from hex string
  1144. // Returns the number of bits loaded (will be chars rounded up to multiple of 4)
  1145. // (0 on failure)
  1146. bit_index_t bit_array_from_hex(BIT_ARRAY* bitarr, bit_index_t offset,
  1147. const char* str, size_t len)
  1148. {
  1149. if(str[0] == '0' && tolower(str[1]) == 'x')
  1150. {
  1151. str += 2;
  1152. len -= 2;
  1153. }
  1154. size_t i;
  1155. for(i = 0; i < len; i++, offset += 4)
  1156. {
  1157. uint8_t b;
  1158. if(bit_array_hex_to_nibble(str[i], &b))
  1159. {
  1160. bit_array_ensure_size(bitarr, offset + 4);
  1161. _set_nibble(bitarr, offset, b);
  1162. }
  1163. else
  1164. {
  1165. break;
  1166. }
  1167. }
  1168. return 4 * i;
  1169. }
  1170. // Returns number of characters written
  1171. size_t bit_array_to_hex(const BIT_ARRAY* bitarr,
  1172. bit_index_t start, bit_index_t length,
  1173. char* str, char uppercase)
  1174. {
  1175. assert(start + length <= bitarr->num_of_bits);
  1176. size_t k = 0;
  1177. bit_index_t offset, end = start + length;
  1178. for(offset = start; offset + WORD_SIZE <= end; offset += WORD_SIZE)
  1179. {
  1180. word_t w = _get_word(bitarr, offset);
  1181. word_offset_t j;
  1182. for(j = 0; j < 64; j += 4)
  1183. {
  1184. str[k++] = bit_array_nibble_to_hex((w>>j) & 0xf, uppercase);
  1185. }
  1186. }
  1187. if(offset < end)
  1188. {
  1189. // Remaining full nibbles (4 bits)
  1190. word_t w = _get_word(bitarr, offset);
  1191. for(; offset + 4 <= end; offset += 4)
  1192. {
  1193. str[k++] = bit_array_nibble_to_hex(w & 0xf, uppercase);
  1194. w >>= 4;
  1195. }
  1196. if(offset < end)
  1197. {
  1198. // Remaining bits
  1199. str[k++] = bit_array_nibble_to_hex(w & bitmask64(end - offset), uppercase);
  1200. }
  1201. }
  1202. str[k] = '\0';
  1203. // Return number of characters written
  1204. return k;
  1205. }
  1206. // Print bit array as hex
  1207. size_t bit_array_print_hex(const BIT_ARRAY* bitarr,
  1208. bit_index_t start, bit_index_t length,
  1209. FILE* fout, char uppercase)
  1210. {
  1211. assert(start + length <= bitarr->num_of_bits);
  1212. size_t k = 0;
  1213. bit_index_t offset, end = start + length;
  1214. for(offset = start; offset + WORD_SIZE <= end; offset += WORD_SIZE)
  1215. {
  1216. word_t w = _get_word(bitarr, offset);
  1217. word_offset_t j;
  1218. for(j = 0; j < 64; j += 4)
  1219. {
  1220. fprintf(fout, "%c", bit_array_nibble_to_hex((w>>j) & 0xf, uppercase));
  1221. k++;
  1222. }
  1223. }
  1224. if(offset < end)
  1225. {
  1226. // Remaining full nibbles (4 bits)
  1227. word_t w = _get_word(bitarr, offset);
  1228. for(; offset + 4 <= end; offset += 4)
  1229. {
  1230. fprintf(fout, "%c", bit_array_nibble_to_hex(w & 0xf, uppercase));
  1231. w >>= 4;
  1232. k++;
  1233. }
  1234. if(offset < end)
  1235. {
  1236. // Remaining bits
  1237. char hex = bit_array_nibble_to_hex(w & bitmask64(end - offset), uppercase);
  1238. fprintf(fout, "%c", hex);
  1239. k++;
  1240. }
  1241. }
  1242. return k;
  1243. }
  1244. //
  1245. // Clone and copy
  1246. //
  1247. // Returns NULL if cannot malloc
  1248. BIT_ARRAY* bit_array_clone(const BIT_ARRAY* bitarr)
  1249. {
  1250. BIT_ARRAY* cpy = bit_array_create(bitarr->num_of_bits);
  1251. if(cpy == NULL)
  1252. {
  1253. return NULL;
  1254. }
  1255. // Copy across bits
  1256. memcpy(cpy->words, bitarr->words, bitarr->num_of_words * sizeof(word_t));
  1257. DEBUG_VALIDATE(cpy);
  1258. return cpy;
  1259. }
  1260. // destination and source may be the same bit_array
  1261. // and src/dst regions may overlap
  1262. static void _array_copy(BIT_ARRAY* dst, bit_index_t dstindx,
  1263. const BIT_ARRAY* src, bit_index_t srcindx,
  1264. bit_index_t length)
  1265. {
  1266. DEBUG_PRINT("bit_array_copy(dst: %zu, src: %zu, length: %zu)\n",
  1267. (size_t)dstindx, (size_t)srcindx, (size_t)length);
  1268. // Num of full words to copy
  1269. word_addr_t num_of_full_words = length / WORD_SIZE;
  1270. word_addr_t i;
  1271. word_offset_t bits_in_last_word = bits_in_top_word(length);
  1272. if(dst == src && srcindx > dstindx)
  1273. {
  1274. // Work left to right
  1275. DEBUG_PRINT("work left to right\n");
  1276. for(i = 0; i < num_of_full_words; i++)
  1277. {
  1278. word_t word = _get_word(src, srcindx+i*WORD_SIZE);
  1279. _set_word(dst, dstindx+i*WORD_SIZE, word);
  1280. }
  1281. if(bits_in_last_word > 0)
  1282. {
  1283. word_t src_word = _get_word(src, srcindx+i*WORD_SIZE);
  1284. word_t dst_word = _get_word(dst, dstindx+i*WORD_SIZE);
  1285. word_t mask = bitmask64(bits_in_last_word);
  1286. word_t word = bitmask_merge(src_word, dst_word, mask);
  1287. _set_word(dst, dstindx+num_of_full_words*WORD_SIZE, word);
  1288. }
  1289. }
  1290. else
  1291. {
  1292. // Work right to left
  1293. DEBUG_PRINT("work right to left\n");
  1294. for(i = 0; i < num_of_full_words; i++)
  1295. {
  1296. word_t word = _get_word(src, srcindx+length-(i+1)*WORD_SIZE);
  1297. _set_word(dst, dstindx+length-(i+1)*WORD_SIZE, word);
  1298. }
  1299. DEBUG_PRINT("Copy %i,%i to %i\n", (int)srcindx, (int)bits_in_last_word,
  1300. (int)dstindx);
  1301. if(bits_in_last_word > 0)
  1302. {
  1303. word_t src_word = _get_word(src, srcindx);
  1304. word_t dst_word = _get_word(dst, dstindx);
  1305. word_t mask = bitmask64(bits_in_last_word);
  1306. word_t word = bitmask_merge(src_word, dst_word, mask);
  1307. _set_word(dst, dstindx, word);
  1308. }
  1309. }
  1310. _mask_top_word(dst);
  1311. }
  1312. // destination and source may be the same bit_array
  1313. // and src/dst regions may overlap
  1314. void bit_array_copy(BIT_ARRAY* dst, bit_index_t dstindx,
  1315. const BIT_ARRAY* src, bit_index_t srcindx,
  1316. bit_index_t length)
  1317. {
  1318. assert(srcindx + length <= src->num_of_bits);
  1319. assert(dstindx <= dst->num_of_bits);
  1320. _array_copy(dst, dstindx, src, srcindx, length);
  1321. DEBUG_VALIDATE(dst);
  1322. }
  1323. // Clone `src` into `dst`. Resizes `dst`.
  1324. void bit_array_copy_all(BIT_ARRAY* dst, const BIT_ARRAY* src)
  1325. {
  1326. bit_array_resize_critical(dst, src->num_of_bits);
  1327. memmove(dst->words, src->words, src->num_of_words * sizeof(word_t));
  1328. DEBUG_VALIDATE(dst);
  1329. }
  1330. //
  1331. // Logic operators
  1332. //
  1333. // Destination can be the same as one or both of the sources
  1334. void bit_array_and(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
  1335. {
  1336. // Ensure dst array is big enough
  1337. word_addr_t max_bits = MAX(src1->num_of_bits, src2->num_of_bits);
  1338. bit_array_ensure_size_critical(dst, max_bits);
  1339. word_addr_t min_words = MIN(src1->num_of_words, src2->num_of_words);
  1340. word_addr_t i;
  1341. for(i = 0; i < min_words; i++)
  1342. {
  1343. dst->words[i] = src1->words[i] & src2->words[i];
  1344. }
  1345. // Set remaining bits to zero
  1346. for(i = min_words; i < dst->num_of_words; i++)
  1347. {
  1348. dst->words[i] = (word_t)0;
  1349. }
  1350. DEBUG_VALIDATE(dst);
  1351. }
  1352. // Destination can be the same as one or both of the sources
  1353. static void _logical_or_xor(BIT_ARRAY* dst,
  1354. const BIT_ARRAY* src1,
  1355. const BIT_ARRAY* src2,
  1356. char use_xor)
  1357. {
  1358. // Ensure dst array is big enough
  1359. bit_array_ensure_size_critical(dst, MAX(src1->num_of_bits, src2->num_of_bits));
  1360. word_addr_t min_words = MIN(src1->num_of_words, src2->num_of_words);
  1361. word_addr_t max_words = MAX(src1->num_of_words, src2->num_of_words);
  1362. word_addr_t i;
  1363. if(use_xor)
  1364. {
  1365. for(i = 0; i < min_words; i++)
  1366. dst->words[i] = src1->words[i] ^ src2->words[i];
  1367. }
  1368. else
  1369. {
  1370. for(i = 0; i < min_words; i++)
  1371. dst->words[i] = src1->words[i] | src2->words[i];
  1372. }
  1373. // Copy remaining bits from longer src array
  1374. if(min_words != max_words)
  1375. {
  1376. const BIT_ARRAY* longer = src1->num_of_words > src2->num_of_words ? src1 : src2;
  1377. for(i = min_words; i < max_words; i++)
  1378. {
  1379. dst->words[i] = longer->words[i];
  1380. }
  1381. }
  1382. // Set remaining bits to zero
  1383. size_t size = (dst->num_of_words - max_words) * sizeof(word_t);
  1384. memset(dst->words + max_words, 0, size);
  1385. DEBUG_VALIDATE(dst);
  1386. }
  1387. void bit_array_or(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
  1388. {
  1389. _logical_or_xor(dst, src1, src2, 0);
  1390. }
  1391. // Destination can be the same as one or both of the sources
  1392. void bit_array_xor(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
  1393. {
  1394. _logical_or_xor(dst, src1, src2, 1);
  1395. }
  1396. // If dst is longer than src, top bits are set to 1
  1397. void bit_array_not(BIT_ARRAY* dst, const BIT_ARRAY* src)
  1398. {
  1399. bit_array_ensure_size_critical(dst, src->num_of_bits);
  1400. word_addr_t i;
  1401. for(i = 0; i < src->num_of_words; i++)
  1402. {
  1403. dst->words[i] = ~(src->words[i]);
  1404. }
  1405. // Set remaining words to 1s
  1406. for(i = src->num_of_words; i < dst->num_of_words; i++)
  1407. {
  1408. dst->words[i] = WORD_MAX;
  1409. }
  1410. _mask_top_word(dst);
  1411. DEBUG_VALIDATE(dst);
  1412. }
  1413. //
  1414. // Comparisons
  1415. //
  1416. // Compare two bit arrays by value stored, with index 0 being the Least
  1417. // Significant Bit (LSB). Arrays do not have to be the same length.
  1418. // Example: ..0101 (5) > ...0011 (3) [index 0 is LSB at right hand side]
  1419. // Sorts on length if all zeros: (0,0) < (0,0,0)
  1420. // returns:
  1421. // >0 iff bitarr1 > bitarr2
  1422. // 0 iff bitarr1 == bitarr2
  1423. // <0 iff bitarr1 < bitarr2
  1424. int bit_array_cmp(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2)
  1425. {
  1426. word_addr_t i;
  1427. word_t word1, word2;
  1428. word_addr_t min_words = bitarr1->num_of_words;
  1429. // i is unsigned so break when i == 0
  1430. if(bitarr1->num_of_words > bitarr2->num_of_words) {
  1431. min_words = bitarr2->num_of_words;
  1432. for(i = bitarr1->num_of_words-1; ; i--) {
  1433. if(bitarr1->words[i]) return 1;
  1434. if(i == bitarr2->num_of_words) break;
  1435. }
  1436. }
  1437. else if(bitarr1->num_of_words < bitarr2->num_of_words) {
  1438. for(i = bitarr2->num_of_words-1; ; i--) {
  1439. if(bitarr2->words[i]) return 1;
  1440. if(i == bitarr1->num_of_words) break;
  1441. }
  1442. }
  1443. if(min_words == 0) return 0;
  1444. for(i = min_words-1; ; i--)
  1445. {
  1446. word1 = bitarr1->words[i];
  1447. word2 = bitarr2->words[i];
  1448. if(word1 != word2) return (word1 > word2 ? 1 : -1);
  1449. if(i == 0) break;
  1450. }
  1451. if(bitarr1->num_of_bits == bitarr2->num_of_bits) return 0;
  1452. return bitarr1->num_of_bits > bitarr2->num_of_bits ? 1 : -1;
  1453. }
  1454. // Compare two bit arrays by value stored, with index 0 being the Most
  1455. // Significant Bit (MSB). Arrays do not have to be the same length.
  1456. // Example: 10.. > 01.. [index 0 is MSB at left hand side]
  1457. // Sorts on length if all zeros: (0,0) < (0,0,0)
  1458. // returns:
  1459. // >0 iff bitarr1 > bitarr2
  1460. // 0 iff bitarr1 == bitarr2
  1461. // <0 iff bitarr1 < bitarr2
  1462. int bit_array_cmp_big_endian(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2)
  1463. {
  1464. word_addr_t min_words = MAX(bitarr1->num_of_words, bitarr2->num_of_words);
  1465. word_addr_t i;
  1466. word_t word1, word2;
  1467. for(i = 0; i < min_words; i++) {
  1468. word1 = _reverse_word(bitarr1->words[i]);
  1469. word2 = _reverse_word(bitarr2->words[i]);
  1470. if(word1 != word2) return (word1 > word2 ? 1 : -1);
  1471. }
  1472. // Check remaining words. Only one of these loops will execute
  1473. for(; i < bitarr1->num_of_words; i++)
  1474. if(bitarr1->words[i]) return 1;
  1475. for(; i < bitarr2->num_of_words; i++)
  1476. if(bitarr2->words[i]) return -1;
  1477. if(bitarr1->num_of_bits == bitarr2->num_of_bits) return 0;
  1478. return bitarr1->num_of_bits > bitarr2->num_of_bits ? 1 : -1;
  1479. }
  1480. // compare bitarr with (bitarr2 << pos)
  1481. // bit_array_cmp(bitarr1, bitarr2<<pos)
  1482. // returns:
  1483. // >0 iff bitarr1 > bitarr2
  1484. // 0 iff bitarr1 == bitarr2
  1485. // <0 iff bitarr1 < bitarr2
  1486. int bit_array_cmp_words(const BIT_ARRAY *arr1,
  1487. bit_index_t pos, const BIT_ARRAY *arr2)
  1488. {
  1489. if(arr1->num_of_bits == 0 && arr2->num_of_bits == 0)
  1490. {
  1491. return 0;
  1492. }
  1493. bit_index_t top_bit1 = 0, top_bit2 = 0;
  1494. char arr1_zero = !bit_array_find_last_set_bit(arr1, &top_bit1);
  1495. char arr2_zero = !bit_array_find_last_set_bit(arr2, &top_bit2);
  1496. if(arr1_zero && arr2_zero) return 0;
  1497. if(arr1_zero) return -1;
  1498. if(arr2_zero) return 1;
  1499. bit_index_t top_bit2_offset = top_bit2 + pos;
  1500. if(top_bit1 != top_bit2_offset) {
  1501. return top_bit1 > top_bit2_offset ? 1 : -1;
  1502. }
  1503. word_addr_t i;
  1504. word_t word1, word2;
  1505. for(i = top_bit2 / WORD_SIZE; i > 0; i--)
  1506. {
  1507. word1 = _get_word(arr1, pos + i * WORD_SIZE);
  1508. word2 = arr2->words[i];
  1509. if(word1 > word2) return 1;
  1510. if(word1 < word2) return -1;
  1511. }
  1512. word1 = _get_word(arr1, pos);
  1513. word2 = arr2->words[0];
  1514. if(word1 > word2) return 1;
  1515. if(word1 < word2) return -1;
  1516. // return 1 if arr1[0..pos] != 0, 0 otherwise
  1517. // Whole words
  1518. word_addr_t num_words = pos / WORD_SIZE;
  1519. for(i = 0; i < num_words; i++)
  1520. {
  1521. if(arr1->words[i] > 0)
  1522. {
  1523. return 1;
  1524. }
  1525. }
  1526. word_offset_t bits_remaining = pos - num_words * WORD_SIZE;
  1527. if(arr1->words[num_words] & bitmask64(bits_remaining))
  1528. {
  1529. return 1;
  1530. }
  1531. return 0;
  1532. }
  1533. //
  1534. // Reverse -- coords may wrap around
  1535. //
  1536. // No bounds checking
  1537. // length cannot be zero
  1538. static void _reverse_region(BIT_ARRAY* bitarr,
  1539. bit_index_t start,
  1540. bit_index_t length)
  1541. {
  1542. bit_index_t left = start;
  1543. bit_index_t right = (start + length - WORD_SIZE) % bitarr->num_of_bits;
  1544. while(length >= 2 * WORD_SIZE)
  1545. {
  1546. // Swap entire words
  1547. word_t left_word = _get_word_cyclic(bitarr, left);
  1548. word_t right_word = _get_word_cyclic(bitarr, right);
  1549. // reverse words individually
  1550. left_word = _reverse_word(left_word);
  1551. right_word = _reverse_word(right_word);
  1552. // Swap
  1553. _set_word_cyclic(bitarr, left, right_word);
  1554. _set_word_cyclic(bitarr, right, left_word);
  1555. // Update
  1556. left = (left + WORD_SIZE) % bitarr->num_of_bits;
  1557. right = (right < WORD_SIZE ? right + bitarr->num_of_bits : right) - WORD_SIZE;
  1558. length -= 2 * WORD_SIZE;
  1559. }
  1560. word_t word, rev;
  1561. if(length == 0)
  1562. {
  1563. return;
  1564. }
  1565. else if(length > WORD_SIZE)
  1566. {
  1567. // Words overlap
  1568. word_t left_word = _get_word_cyclic(bitarr, left);
  1569. word_t right_word = _get_word_cyclic(bitarr, right);
  1570. rev = _reverse_word(left_word);
  1571. right_word = _reverse_word(right_word);
  1572. // fill left 64 bits with right word rev
  1573. _set_word_cyclic(bitarr, left, right_word);
  1574. // Now do remaining bits (length is between 1 and 64 bits)
  1575. left += WORD_SIZE;
  1576. length -= WORD_SIZE;
  1577. word = _get_word_cyclic(bitarr, left);
  1578. }
  1579. else
  1580. {
  1581. word = _get_word_cyclic(bitarr, left);
  1582. rev = _reverse_word(word);
  1583. }
  1584. rev >>= WORD_SIZE - length;
  1585. word_t mask = bitmask64(length);
  1586. word = bitmask_merge(rev, word, mask);
  1587. _set_word_cyclic(bitarr, left, word);
  1588. }
  1589. void bit_array_reverse_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len)
  1590. {
  1591. assert(start + len <= bitarr->num_of_bits);
  1592. if(len > 0) _reverse_region(bitarr, start, len);
  1593. DEBUG_VALIDATE(bitarr);
  1594. }
  1595. void bit_array_reverse(BIT_ARRAY* bitarr)
  1596. {
  1597. if(bitarr->num_of_bits > 0) _reverse_region(bitarr, 0, bitarr->num_of_bits);
  1598. DEBUG_VALIDATE(bitarr);
  1599. }
  1600. //
  1601. // Shift left / right
  1602. //
  1603. // Shift towards MSB / higher index
  1604. void bit_array_shift_left(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill)
  1605. {
  1606. if(shift_dist >= bitarr->num_of_bits)
  1607. {
  1608. fill ? bit_array_set_all(bitarr) : bit_array_clear_all(bitarr);
  1609. return;
  1610. }
  1611. else if(shift_dist == 0)
  1612. {
  1613. return;
  1614. }
  1615. FillAction action = fill ? FILL_REGION : ZERO_REGION;
  1616. bit_index_t cpy_length = bitarr->num_of_bits - shift_dist;
  1617. _array_copy(bitarr, shift_dist, bitarr, 0, cpy_length);
  1618. _set_region(bitarr, 0, shift_dist, action);
  1619. }
  1620. // shift left extend - don't truncate bits when shifting UP, instead
  1621. // make room for them.
  1622. void bit_array_shift_left_extend(BIT_ARRAY* bitarr, bit_index_t shift_dist,
  1623. char fill)
  1624. {
  1625. bit_index_t newlen = bitarr->num_of_bits + shift_dist;
  1626. bit_index_t cpy_length = bitarr->num_of_bits;
  1627. if(shift_dist == 0)
  1628. {
  1629. return;
  1630. }
  1631. bit_array_resize_critical(bitarr, newlen);
  1632. FillAction action = fill ? FILL_REGION : ZERO_REGION;
  1633. _array_copy(bitarr, shift_dist, bitarr, 0, cpy_length);
  1634. _set_region(bitarr, 0, shift_dist, action);
  1635. }
  1636. // Shift towards LSB / lower index
  1637. void bit_array_shift_right(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill)
  1638. {
  1639. if(shift_dist >= bitarr->num_of_bits)
  1640. {
  1641. fill ? bit_array_set_all(bitarr) : bit_array_clear_all(bitarr);
  1642. return;
  1643. }
  1644. else if(shift_dist == 0)
  1645. {
  1646. return;
  1647. }
  1648. FillAction action = fill ? FILL_REGION : ZERO_REGION;
  1649. bit_index_t cpy_length = bitarr->num_of_bits - shift_dist;
  1650. bit_array_copy(bitarr, 0, bitarr, shift_dist, cpy_length);
  1651. _set_region(bitarr, cpy_length, shift_dist, action);
  1652. }
  1653. //
  1654. // Cycle
  1655. //
  1656. // Cycle towards index 0
  1657. void bit_array_cycle_right(BIT_ARRAY* bitarr, bit_index_t cycle_dist)
  1658. {
  1659. if(bitarr->num_of_bits == 0)
  1660. {
  1661. return;
  1662. }
  1663. cycle_dist = cycle_dist % bitarr->num_of_bits;
  1664. if(cycle_dist == 0)
  1665. {
  1666. return;
  1667. }
  1668. bit_index_t len1 = cycle_dist;
  1669. bit_index_t len2 = bitarr->num_of_bits - cycle_dist;
  1670. _reverse_region(bitarr, 0, len1);
  1671. _reverse_region(bitarr, len1, len2);
  1672. bit_array_reverse(bitarr);
  1673. }
  1674. // Cycle away from index 0
  1675. void bit_array_cycle_left(BIT_ARRAY* bitarr, bit_index_t cycle_dist)
  1676. {
  1677. if(bitarr->num_of_bits == 0)
  1678. {
  1679. return;
  1680. }
  1681. cycle_dist = cycle_dist % bitarr->num_of_bits;
  1682. if(cycle_dist == 0)
  1683. {
  1684. return;
  1685. }
  1686. bit_index_t len1 = bitarr->num_of_bits - cycle_dist;
  1687. bit_index_t len2 = cycle_dist;
  1688. _reverse_region(bitarr, 0, len1);
  1689. _reverse_region(bitarr, len1, len2);
  1690. bit_array_reverse(bitarr);
  1691. }
  1692. //
  1693. // Next permutation
  1694. //
  1695. static word_t _next_permutation(word_t v)
  1696. {
  1697. // From http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
  1698. word_t t = v | (v - 1); // t gets v's least significant 0 bits set to 1
  1699. // Next set to 1 the most significant bit to change,
  1700. // set to 0 the least significant ones, and add the necessary 1 bits.
  1701. return (t+1) | (((~t & (t+1)) - 1) >> (trailing_zeros(v) + 1));
  1702. }
  1703. // Get the next permutation of an array with a fixed size and given number of
  1704. // bits set. Also known as next lexicographic permutation.
  1705. // Given a bit array find the next lexicographic orginisation of the bits
  1706. // Number of possible combinations given by (size choose bits_set) i.e. nCk
  1707. // 00011 -> 00101 -> 00110 -> 01001 -> 01010 ->
  1708. // 01100 -> 10001 -> 10010 -> 10100 -> 11000 -> 00011 (back to start)
  1709. void bit_array_next_permutation(BIT_ARRAY* bitarr)
  1710. {
  1711. if(bitarr->num_of_bits == 0)
  1712. {
  1713. return;
  1714. }
  1715. word_addr_t w;
  1716. char carry = 0;
  1717. word_offset_t top_bits = bitset64_idx(bitarr->num_of_bits);
  1718. for(w = 0; w < bitarr->num_of_words; w++)
  1719. {
  1720. word_t mask
  1721. = (w < bitarr->num_of_words - 1 || top_bits == 0) ? WORD_MAX
  1722. : bitmask64(top_bits);
  1723. if(bitarr->words[w] > 0 &&
  1724. (bitarr->words[w] | (bitarr->words[w]-1)) == mask)
  1725. {
  1726. // Bits in this word cannot be moved forward
  1727. carry = 1;
  1728. }
  1729. else if(carry)
  1730. {
  1731. // 0111 -> 1000, 1000 -> 1001
  1732. word_t tmp = bitarr->words[w] + 1;
  1733. // Count bits previously set
  1734. bit_index_t bits_previously_set = POPCOUNT(bitarr->words[w]);
  1735. // set new word
  1736. bitarr->words[w] = tmp;
  1737. // note: w is unsigned
  1738. // Zero words while counting bits set
  1739. while(w > 0)
  1740. {
  1741. bits_previously_set += POPCOUNT(bitarr->words[w-1]);
  1742. bitarr->words[w-1] = 0;
  1743. w--;
  1744. }
  1745. // Set bits at the beginning
  1746. SET_REGION(bitarr, 0, bits_previously_set - POPCOUNT(tmp));
  1747. carry = 0;
  1748. break;
  1749. }
  1750. else if(bitarr->words[w] > 0)
  1751. {
  1752. bitarr->words[w] = _next_permutation(bitarr->words[w]);
  1753. break;
  1754. }
  1755. }
  1756. if(carry)
  1757. {
  1758. // Loop around
  1759. bit_index_t num_bits_set = bit_array_num_bits_set(bitarr);
  1760. bit_array_clear_all(bitarr);
  1761. SET_REGION(bitarr, 0, num_bits_set);
  1762. }
  1763. DEBUG_VALIDATE(bitarr);
  1764. }
  1765. //
  1766. // Interleave
  1767. //
  1768. // dst cannot point to the same bit array as src1 or src2
  1769. // src1, src2 may point to the same bit array
  1770. // abcd 1234 -> a1b2c3d4
  1771. // 0011 0000 -> 00001010
  1772. // 1111 0000 -> 10101010
  1773. // 0101 1010 -> 01100110
  1774. void bit_array_interleave(BIT_ARRAY* dst,
  1775. const BIT_ARRAY* src1,
  1776. const BIT_ARRAY* src2)
  1777. {
  1778. // dst cannot be either src1 or src2
  1779. assert(dst != src1 && dst != src2);
  1780. // Behaviour undefined when src1 length != src2 length",
  1781. assert(src1->num_of_bits == src2->num_of_bits);
  1782. // Need at least src1->num_of_words + src2->num_of_words
  1783. size_t nwords = MIN(src1->num_of_words + src2->num_of_words, 2);
  1784. _bit_array_ensure_nwords(dst, nwords, __FILE__, __LINE__, __func__);
  1785. dst->num_of_bits = src1->num_of_bits + src2->num_of_bits;
  1786. dst->num_of_words = roundup_bits2words64(dst->num_of_bits);
  1787. word_addr_t i, j;
  1788. for(i = 0, j = 0; i < src1->num_of_words; i++)
  1789. {
  1790. word_t a = src1->words[i];
  1791. word_t b = src2->words[i];
  1792. dst->words[j++] = morton_table0[(a ) & 0xff] |
  1793. morton_table1[(b ) & 0xff] |
  1794. (morton_table0[(a >> 8) & 0xff] << 16) |
  1795. (morton_table1[(b >> 8) & 0xff] << 16) |
  1796. (morton_table0[(a >> 16) & 0xff] << 32) |
  1797. (morton_table1[(b >> 16) & 0xff] << 32) |
  1798. (morton_table0[(a >> 24) & 0xff] << 48) |
  1799. (morton_table1[(b >> 24) & 0xff] << 48);
  1800. dst->words[j++] = morton_table0[(a >> 32) & 0xff] |
  1801. morton_table1[(b >> 32) & 0xff] |
  1802. (morton_table0[(a >> 40) & 0xff] << 16) |
  1803. (morton_table1[(b >> 40) & 0xff] << 16) |
  1804. (morton_table0[(a >> 48) & 0xff] << 32) |
  1805. (morton_table1[(b >> 48) & 0xff] << 32) |
  1806. (morton_table0[(a >> 56) ] << 48) |
  1807. (morton_table1[(b >> 56) ] << 48);
  1808. }
  1809. DEBUG_VALIDATE(dst);
  1810. }
  1811. //
  1812. // Random
  1813. //
  1814. // Set bits randomly with probability prob : 0 <= prob <= 1
  1815. void bit_array_random(BIT_ARRAY* bitarr, float prob)
  1816. {
  1817. assert(prob >= 0 && prob <= 1);
  1818. if(bitarr->num_of_bits == 0)
  1819. {
  1820. return;
  1821. }
  1822. else if(prob == 1)
  1823. {
  1824. bit_array_set_all(bitarr);
  1825. return;
  1826. }
  1827. // rand() generates number between 0 and RAND_MAX inclusive
  1828. // therefore we want to check if rand() <= p
  1829. long p = RAND_MAX * prob;
  1830. _seed_rand();
  1831. word_addr_t w;
  1832. word_offset_t o;
  1833. // Initialise to zero
  1834. memset(bitarr->words, 0, bitarr->num_of_words * sizeof(word_t));
  1835. for(w = 0; w < bitarr->num_of_words - 1; w++)
  1836. {
  1837. for(o = 0; o < WORD_SIZE; o++)
  1838. {
  1839. if(rand() <= p)
  1840. {
  1841. bitarr->words[w] |= ((word_t)0x1 << o);
  1842. }
  1843. }
  1844. }
  1845. // Top word
  1846. word_offset_t bits_in_last_word = bits_in_top_word(bitarr->num_of_bits);
  1847. w = bitarr->num_of_words - 1;
  1848. for(o = 0; o < bits_in_last_word; o++)
  1849. {
  1850. if(rand() <= p)
  1851. {
  1852. bitarr->words[w] |= ((word_t)0x1 << o);
  1853. }
  1854. }
  1855. DEBUG_VALIDATE(bitarr);
  1856. }
  1857. // Shuffle the bits in an array randomly
  1858. void bit_array_shuffle(BIT_ARRAY* bitarr)
  1859. {
  1860. if(bitarr->num_of_bits == 0)
  1861. return;
  1862. _seed_rand();
  1863. bit_index_t i, j;
  1864. for(i = bitarr->num_of_bits - 1; i > 0; i--)
  1865. {
  1866. j = (bit_index_t)rand() % i;
  1867. // Swap i and j
  1868. char x = (bitarr->words[bitset64_wrd(i)] >> bitset64_idx(i)) & 0x1;
  1869. char y = (bitarr->words[bitset64_wrd(j)] >> bitset64_idx(j)) & 0x1;
  1870. if(!y)
  1871. bitarr->words[bitset64_wrd(i)] &= ~((word_t)0x1 << bitset64_idx(i));
  1872. else
  1873. bitarr->words[bitset64_wrd(i)] |= (word_t)0x1 << bitset64_idx(i);
  1874. if(!x)
  1875. bitarr->words[bitset64_wrd(j)] &= ~((word_t)0x1 << bitset64_idx(j));
  1876. else
  1877. bitarr->words[bitset64_wrd(j)] |= (word_t)0x1 << bitset64_idx(j);
  1878. }
  1879. DEBUG_VALIDATE(bitarr);
  1880. }
  1881. //
  1882. // Arithmetic
  1883. //
  1884. // Returns 1 on sucess, 0 if value in array is too big
  1885. char bit_array_as_num(const BIT_ARRAY* bitarr, uint64_t* result)
  1886. {
  1887. if(bitarr->num_of_bits == 0)
  1888. {
  1889. *result = 0;
  1890. return 1;
  1891. }
  1892. word_addr_t w;
  1893. for(w = bitarr->num_of_words-1; w > 0; w--)
  1894. {
  1895. if(bitarr->words[w] > 0)
  1896. {
  1897. return 0;
  1898. }
  1899. }
  1900. *result = bitarr->words[0];
  1901. return 1;
  1902. }
  1903. // 1 iff bitarr > value
  1904. // 0 iff bitarr == value
  1905. // -1 iff bitarr < value
  1906. int bit_array_cmp_uint64(const BIT_ARRAY* bitarr, uint64_t value)
  1907. {
  1908. uint64_t arr_num = 0;
  1909. // If cannot put bitarr in uint64, it is > value
  1910. if(!bit_array_as_num(bitarr, &arr_num)) return 1;
  1911. if(arr_num > value) return 1;
  1912. else if(arr_num < value) return -1;
  1913. else return 0;
  1914. }
  1915. // If value is zero, no change is made
  1916. void bit_array_add_uint64(BIT_ARRAY* bitarr, uint64_t value)
  1917. {
  1918. if(value == 0)
  1919. {
  1920. return;
  1921. }
  1922. else if(bitarr->num_of_bits == 0)
  1923. {
  1924. bit_array_resize_critical(bitarr, WORD_SIZE - leading_zeros(value));
  1925. bitarr->words[0] = (word_t)value;
  1926. return;
  1927. }
  1928. char carry = 0;
  1929. word_addr_t i;
  1930. for(i = 0; i < bitarr->num_of_words; i++)
  1931. {
  1932. if(WORD_MAX - bitarr->words[i] < value)
  1933. {
  1934. carry = 1;
  1935. bitarr->words[i] += value;
  1936. }
  1937. else
  1938. {
  1939. // Carry is absorbed
  1940. bitarr->words[i] += value;
  1941. carry = 0;
  1942. break;
  1943. }
  1944. }
  1945. if(carry)
  1946. {
  1947. // Bit array full, need another bit after all words filled
  1948. bit_array_resize_critical(bitarr, bitarr->num_of_words * WORD_SIZE + 1);
  1949. // Set top word to 1
  1950. bitarr->words[bitarr->num_of_words-1] = 1;
  1951. }
  1952. else
  1953. {
  1954. word_t final_word = bitarr->words[bitarr->num_of_words-1];
  1955. word_offset_t expected_bits = bits_in_top_word(bitarr->num_of_bits);
  1956. word_offset_t actual_bits = WORD_SIZE - leading_zeros(final_word);
  1957. if(actual_bits > expected_bits)
  1958. {
  1959. // num_of_bits has increased -- num_of_words has not
  1960. bitarr->num_of_bits += (actual_bits - expected_bits);
  1961. }
  1962. }
  1963. }
  1964. // If value is greater than bitarr, bitarr is not changed and 0 is returned
  1965. // Returns 1 on success, 0 if value > bitarr
  1966. char bit_array_sub_uint64(BIT_ARRAY* bitarr, uint64_t value)
  1967. {
  1968. if(value == 0)
  1969. {
  1970. return 1;
  1971. }
  1972. else if(bitarr->words[0] >= value)
  1973. {
  1974. bitarr->words[0] -= value;
  1975. return 1;
  1976. }
  1977. value -= bitarr->words[0];
  1978. word_addr_t i;
  1979. for(i = 1; i < bitarr->num_of_words; i++)
  1980. {
  1981. if(bitarr->words[i] > 0)
  1982. {
  1983. // deduct one
  1984. bitarr->words[i]--;
  1985. for(; i > 0; i--)
  1986. {
  1987. bitarr->words[i] = WORD_MAX;
  1988. }
  1989. // -1 since we've already deducted 1
  1990. bitarr->words[0] = WORD_MAX - value - 1;
  1991. return 1;
  1992. }
  1993. }
  1994. // subtract value is greater than array
  1995. return 0;
  1996. }
  1997. //
  1998. // Arithmetic between bit arrays
  1999. //
  2000. // src1, src2 and dst can all be the same BIT_ARRAY
  2001. static void _arithmetic(BIT_ARRAY* dst,
  2002. const BIT_ARRAY* src1,
  2003. const BIT_ARRAY* src2,
  2004. char subtract)
  2005. {
  2006. word_addr_t max_words = MAX(src1->num_of_words, src2->num_of_words);
  2007. // Adding: dst_words >= max(src1 words, src2 words)
  2008. // Subtracting: dst_words is >= src1->num_of_words
  2009. char carry = subtract ? 1 : 0;
  2010. word_addr_t i;
  2011. word_t word1, word2;
  2012. for(i = 0; i < max_words; i++)
  2013. {
  2014. word1 = (i < src1->num_of_words ? src1->words[i] : 0);
  2015. word2 = (i < src2->num_of_words ? src2->words[i] : 0);
  2016. if(subtract)
  2017. word2 = ~word2;
  2018. dst->words[i] = word1 + word2 + carry;
  2019. // Update carry
  2020. carry = WORD_MAX - word1 < word2 || WORD_MAX - word1 - word2 < (word_t)carry;
  2021. }
  2022. if(subtract)
  2023. {
  2024. carry = 0;
  2025. }
  2026. else
  2027. {
  2028. // Check last word
  2029. word_offset_t bits_on_last_word = bits_in_top_word(dst->num_of_bits);
  2030. if(bits_on_last_word < WORD_SIZE)
  2031. {
  2032. word_t mask = bitmask64(bits_on_last_word);
  2033. if(dst->words[max_words-1] > mask)
  2034. {
  2035. // Array has overflowed, increase size
  2036. dst->num_of_bits++;
  2037. }
  2038. }
  2039. else if(carry)
  2040. {
  2041. // Carry onto a new word
  2042. if(dst->num_of_words == max_words)
  2043. {
  2044. // Need to resize for the carry bit
  2045. bit_array_resize_critical(dst, dst->num_of_bits+1);
  2046. }
  2047. dst->words[max_words] = (word_t)1;
  2048. }
  2049. }
  2050. // Zero the rest of dst array
  2051. for(i = max_words+carry; i < dst->num_of_words; i++)
  2052. {
  2053. dst->words[i] = (word_t)0;
  2054. }
  2055. DEBUG_VALIDATE(dst);
  2056. }
  2057. // src1, src2 and dst can all be the same BIT_ARRAY
  2058. // If dst is shorter than either of src1, src2, it is enlarged
  2059. void bit_array_add(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
  2060. {
  2061. bit_array_ensure_size_critical(dst, MAX(src1->num_of_bits, src2->num_of_bits));
  2062. _arithmetic(dst, src1, src2, 0);
  2063. }
  2064. // dst = src1 - src2
  2065. // src1, src2 and dst can all be the same BIT_ARRAY
  2066. // If dst is shorter than src1, it will be extended to be as long as src1
  2067. // src1 must be greater than or equal to src2 (src1 >= src2)
  2068. void bit_array_subtract(BIT_ARRAY* dst,
  2069. const BIT_ARRAY* src1, const BIT_ARRAY* src2)
  2070. {
  2071. // subtraction by method of complements:
  2072. // a - b = a + ~b + 1 = src1 + ~src2 +1
  2073. assert(bit_array_cmp(src1, src2) >= 0); // Require src1 >= src2
  2074. bit_array_ensure_size_critical(dst, src1->num_of_bits);
  2075. _arithmetic(dst, src1, src2, 1);
  2076. }
  2077. // Add `add` to `bitarr` at `pos`
  2078. // Bounds checking not needed as out of bounds is valid
  2079. void bit_array_add_word(BIT_ARRAY *bitarr, bit_index_t pos, uint64_t add)
  2080. {
  2081. DEBUG_VALIDATE(bitarr);
  2082. if(add == 0)
  2083. {
  2084. return;
  2085. }
  2086. else if(pos >= bitarr->num_of_bits)
  2087. {
  2088. // Resize and add!
  2089. bit_index_t num_bits_required = pos + (WORD_SIZE - leading_zeros(add));
  2090. bit_array_resize_critical(bitarr, num_bits_required);
  2091. _set_word(bitarr, pos, (word_t)add);
  2092. return;
  2093. }
  2094. /*
  2095. char str[1000];
  2096. printf(" add_word: %s\n", bit_array_to_str_rev(bitarr, str));
  2097. printf(" word: %s [pos: %i]\n", _word_to_str(add, str), (int)pos);
  2098. */
  2099. word_t w = _get_word(bitarr, pos);
  2100. word_t sum = w + add;
  2101. char carry = WORD_MAX - w < add;
  2102. // Ensure array is big enough
  2103. bit_index_t num_bits_required = pos + (carry ? WORD_SIZE + 1
  2104. : (WORD_SIZE - leading_zeros(sum)));
  2105. bit_array_ensure_size(bitarr, num_bits_required);
  2106. _set_word(bitarr, pos, sum);
  2107. pos += WORD_SIZE;
  2108. if(carry)
  2109. {
  2110. word_offset_t offset = pos % WORD_SIZE;
  2111. word_addr_t addr = bitset64_wrd(pos);
  2112. add = (word_t)0x1 << offset;
  2113. carry = (WORD_MAX - bitarr->words[addr] < add);
  2114. sum = bitarr->words[addr] + add;
  2115. num_bits_required = addr * WORD_SIZE +
  2116. (carry ? WORD_SIZE + 1 : (WORD_SIZE - leading_zeros(sum)));
  2117. bit_array_ensure_size(bitarr, num_bits_required);
  2118. bitarr->words[addr++] = sum;
  2119. if(carry)
  2120. {
  2121. while(addr < bitarr->num_of_words && bitarr->words[addr] == WORD_MAX)
  2122. {
  2123. bitarr->words[addr++] = 0;
  2124. }
  2125. if(addr == bitarr->num_of_words)
  2126. {
  2127. bit_array_resize_critical(bitarr, addr * WORD_SIZE + 1);
  2128. }
  2129. else if(addr == bitarr->num_of_words-1 &&
  2130. bitarr->words[addr] == bitmask64(bits_in_top_word(bitarr->num_of_bits)))
  2131. {
  2132. bit_array_resize_critical(bitarr, bitarr->num_of_bits + 1);
  2133. }
  2134. bitarr->words[addr]++;
  2135. }
  2136. }
  2137. DEBUG_VALIDATE(bitarr);
  2138. }
  2139. // Add `add` to `bitarr` at `pos`
  2140. // Bounds checking not needed as out of bounds is valid
  2141. void bit_array_add_words(BIT_ARRAY *bitarr, bit_index_t pos, const BIT_ARRAY *add)
  2142. {
  2143. assert(bitarr != add); // bitarr and add cannot point to the same bit array
  2144. bit_index_t add_top_bit_set;
  2145. if(!bit_array_find_last_set_bit(add, &add_top_bit_set))
  2146. {
  2147. // No bits set in add
  2148. return;
  2149. }
  2150. else if(pos >= bitarr->num_of_bits)
  2151. {
  2152. // Just resize and copy!
  2153. bit_index_t num_bits_required = pos + add_top_bit_set + 1;
  2154. bit_array_resize_critical(bitarr, num_bits_required);
  2155. _array_copy(bitarr, pos, add, 0, add->num_of_bits);
  2156. return;
  2157. }
  2158. else if(pos == 0)
  2159. {
  2160. bit_array_add(bitarr, bitarr, add);
  2161. return;
  2162. }
  2163. /*
  2164. char str[1000];
  2165. printf(" add_words1: %s\n", bit_array_to_str_rev(bitarr, str));
  2166. printf(" add_words2: %s\n", bit_array_to_str_rev(add, str));
  2167. printf(" [pos: %i]\n", (int)pos);
  2168. */
  2169. bit_index_t num_bits_required = pos + add_top_bit_set + 1;
  2170. bit_array_ensure_size(bitarr, num_bits_required);
  2171. word_addr_t first_word = bitset64_wrd(pos);
  2172. word_offset_t first_offset = bitset64_idx(pos);
  2173. word_t w = add->words[0] << first_offset;
  2174. unsigned char carry = (WORD_MAX - bitarr->words[first_word] < w);
  2175. bitarr->words[first_word] += w;
  2176. word_addr_t i = first_word + 1;
  2177. bit_index_t offset = WORD_SIZE - first_offset;
  2178. for(; carry || offset <= add_top_bit_set; i++, offset += WORD_SIZE)
  2179. {
  2180. w = offset < add->num_of_bits ? _get_word(add, offset) : (word_t)0;
  2181. if(i >= bitarr->num_of_words)
  2182. {
  2183. // Extend by a word
  2184. bit_array_resize_critical(bitarr, (bit_index_t)(i+1)*WORD_SIZE+1);
  2185. }
  2186. word_t prev = bitarr->words[i];
  2187. bitarr->words[i] += w + carry;
  2188. carry = (WORD_MAX - prev < w || (carry && prev + w == WORD_MAX)) ? 1 : 0;
  2189. }
  2190. word_offset_t top_bits
  2191. = WORD_SIZE - leading_zeros(bitarr->words[bitarr->num_of_words-1]);
  2192. bit_index_t min_bits = (bitarr->num_of_words-1)*WORD_SIZE + top_bits;
  2193. if(bitarr->num_of_bits < min_bits)
  2194. {
  2195. // Extend within the last word
  2196. bitarr->num_of_bits = min_bits;
  2197. }
  2198. DEBUG_VALIDATE(bitarr);
  2199. }
  2200. char bit_array_sub_word(BIT_ARRAY* bitarr, bit_index_t pos, word_t minus)
  2201. {
  2202. DEBUG_VALIDATE(bitarr);
  2203. if(minus == 0)
  2204. {
  2205. return 1;
  2206. }
  2207. word_t w = _get_word(bitarr, pos);
  2208. if(w >= minus)
  2209. {
  2210. _set_word(bitarr, pos, w - minus);
  2211. DEBUG_VALIDATE(bitarr);
  2212. return 1;
  2213. }
  2214. minus -= w;
  2215. bit_index_t offset;
  2216. for(offset = pos + WORD_SIZE; offset < bitarr->num_of_bits; offset += WORD_SIZE)
  2217. {
  2218. w = _get_word(bitarr, offset);
  2219. if(w > 0)
  2220. {
  2221. // deduct one
  2222. _set_word(bitarr, offset, w - 1);
  2223. SET_REGION(bitarr, pos, offset-pos);
  2224. // -1 since we've already deducted 1
  2225. minus--;
  2226. _set_word(bitarr, pos, WORD_MAX - minus);
  2227. DEBUG_VALIDATE(bitarr);
  2228. return 1;
  2229. }
  2230. }
  2231. DEBUG_VALIDATE(bitarr);
  2232. return 0;
  2233. }
  2234. char bit_array_sub_words(BIT_ARRAY* bitarr, bit_index_t pos, BIT_ARRAY* minus)
  2235. {
  2236. assert(bitarr != minus); // bitarr and minus cannot point to the same bit array
  2237. int cmp = bit_array_cmp_words(bitarr, pos, minus);
  2238. if(cmp == 0)
  2239. {
  2240. bit_array_clear_all(bitarr);
  2241. return 1;
  2242. }
  2243. else if(cmp < 0)
  2244. {
  2245. return 0;
  2246. }
  2247. bit_index_t bitarr_length = bitarr->num_of_bits;
  2248. bit_index_t bitarr_top_bit_set;
  2249. bit_array_find_last_set_bit(bitarr, &bitarr_top_bit_set);
  2250. // subtraction by method of complements:
  2251. // a - b = a + ~b + 1 = src1 + ~src2 +1
  2252. bit_array_not(minus, minus);
  2253. bit_array_add_words(bitarr, pos, minus);
  2254. bit_array_add_word(bitarr, pos, (word_t)1);
  2255. bit_array_sub_word(bitarr, pos+minus->num_of_bits, 1);
  2256. bit_array_resize(bitarr, bitarr_length);
  2257. bit_array_not(minus, minus);
  2258. DEBUG_VALIDATE(bitarr);
  2259. return 1;
  2260. }
  2261. void bit_array_mul_uint64(BIT_ARRAY *bitarr, uint64_t multiplier)
  2262. {
  2263. if(bitarr->num_of_bits == 0 || multiplier == 1)
  2264. {
  2265. return;
  2266. }
  2267. else if(multiplier == 0)
  2268. {
  2269. bit_array_clear_all(bitarr);
  2270. return;
  2271. }
  2272. bit_index_t i;
  2273. for(i = bitarr->num_of_bits; i > 0; i--)
  2274. {
  2275. if(bit_array_get(bitarr, i-1))
  2276. {
  2277. bit_array_clear(bitarr, i-1);
  2278. bit_array_add_word(bitarr, i-1, multiplier);
  2279. }
  2280. }
  2281. DEBUG_VALIDATE(bitarr);
  2282. }
  2283. void bit_array_multiply(BIT_ARRAY *dst, BIT_ARRAY *src1, BIT_ARRAY *src2)
  2284. {
  2285. if(src1->num_of_bits == 0 || src2->num_of_bits == 0)
  2286. {
  2287. bit_array_clear_all(dst);
  2288. return;
  2289. }
  2290. // Cannot pass the same array as dst, src1 AND src2
  2291. assert(dst != src1 || dst != src2);
  2292. // Dev: multiplier == 1?
  2293. BIT_ARRAY *read_arr, *add_arr;
  2294. if(src1 == dst)
  2295. {
  2296. read_arr = src1;
  2297. add_arr = src2;
  2298. }
  2299. else
  2300. {
  2301. read_arr = src2;
  2302. add_arr = src1;
  2303. }
  2304. if(dst != src1 && dst != src2)
  2305. {
  2306. bit_array_clear_all(dst);
  2307. }
  2308. bit_index_t i;
  2309. for(i = read_arr->num_of_bits; i > 0; i--)
  2310. {
  2311. if(bit_array_get(read_arr, i-1))
  2312. {
  2313. bit_array_clear(dst, i-1);
  2314. bit_array_add_words(dst, i-1, add_arr);
  2315. }
  2316. }
  2317. DEBUG_VALIDATE(dst);
  2318. }
  2319. // bitarr = round_down(bitarr / divisor)
  2320. // rem = bitarr % divisor
  2321. void bit_array_div_uint64(BIT_ARRAY *bitarr, uint64_t divisor, uint64_t *rem)
  2322. {
  2323. assert(divisor != 0); // cannot divide by zero
  2324. bit_index_t div_top_bit = 63 - leading_zeros(divisor);
  2325. bit_index_t bitarr_top_bit;
  2326. if(!bit_array_find_last_set_bit(bitarr, &bitarr_top_bit))
  2327. {
  2328. *rem = 0;
  2329. return;
  2330. }
  2331. if(bitarr_top_bit < div_top_bit)
  2332. {
  2333. *rem = bitarr->words[0];
  2334. bit_array_clear_all(bitarr);
  2335. return;
  2336. }
  2337. // When div is shifted by offset, their top set bits are aligned
  2338. bit_index_t offset = bitarr_top_bit - div_top_bit;
  2339. uint64_t tmp = _get_word(bitarr, offset);
  2340. _set_word(bitarr, offset, (word_t)0);
  2341. // Carry if 1 if the top bit was set before left shift
  2342. char carry = 0;
  2343. // offset unsigned so break when offset == 0
  2344. while(1)
  2345. {
  2346. if(carry)
  2347. {
  2348. // (carry:tmp) - divisor = (WORD_MAX+1+tmp)-divisor
  2349. tmp = WORD_MAX - divisor + tmp + 1;
  2350. bit_array_set(bitarr, offset);
  2351. }
  2352. else if(tmp >= divisor)
  2353. {
  2354. tmp -= divisor;
  2355. bit_array_set(bitarr, offset);
  2356. }
  2357. else
  2358. {
  2359. bit_array_clear(bitarr, offset);
  2360. }
  2361. if(offset == 0)
  2362. break;
  2363. offset--;
  2364. // Is the top bit set (that we're about to shift off)?
  2365. carry = tmp & 0x8000000000000000;
  2366. tmp <<= 1;
  2367. tmp |= bit_array_get(bitarr, offset);
  2368. }
  2369. *rem = tmp;
  2370. }
  2371. // Results in:
  2372. // quotient = dividend / divisor
  2373. // dividend = dividend % divisor
  2374. // (dividend is used to return the remainder)
  2375. void bit_array_divide(BIT_ARRAY *dividend, BIT_ARRAY *quotient, BIT_ARRAY *divisor)
  2376. {
  2377. assert(bit_array_cmp_uint64(divisor, 0) != 0); // Cannot divide by zero
  2378. bit_array_clear_all(quotient);
  2379. int cmp = bit_array_cmp(dividend, divisor);
  2380. if(cmp == 0)
  2381. {
  2382. bit_array_ensure_size(quotient, 1);
  2383. bit_array_set(quotient, 0);
  2384. bit_array_clear_all(dividend);
  2385. return;
  2386. }
  2387. else if(cmp < 0)
  2388. {
  2389. // dividend is < divisor, quotient is zero -- done
  2390. return;
  2391. }
  2392. // now we know: dividend > divisor, quotient is zero'd,
  2393. // dividend != 0, divisor != 0
  2394. bit_index_t dividend_top_bit = 0, div_top_bit = 0;
  2395. bit_array_find_last_set_bit(dividend, &dividend_top_bit);
  2396. bit_array_find_last_set_bit(divisor, &div_top_bit);
  2397. // When divisor is shifted by offset, their top set bits are aligned
  2398. bit_index_t offset = dividend_top_bit - div_top_bit;
  2399. // offset unsigned so break when offset == 0
  2400. for(; ; offset--)
  2401. {
  2402. if(bit_array_cmp_words(dividend, offset, divisor) >= 0)
  2403. {
  2404. bit_array_sub_words(dividend, offset, divisor);
  2405. bit_array_ensure_size(quotient, offset+1);
  2406. bit_array_set(quotient, offset);
  2407. }
  2408. if(offset == 0)
  2409. break;
  2410. }
  2411. }
  2412. //
  2413. // Read/Write from files
  2414. //
  2415. // file format is [8 bytes: for number of elements in array][data]
  2416. // data is written in little endian order (least sig byte first)
  2417. //
  2418. // Saves bit array to a file. Returns the number of bytes written
  2419. // number of bytes returned should be 8+(bitarr->num_of_bits+7)/8
  2420. bit_index_t bit_array_save(const BIT_ARRAY* bitarr, FILE* f)
  2421. {
  2422. bit_index_t num_of_bytes = roundup_bits2bytes(bitarr->num_of_bits);
  2423. bit_index_t bytes_written = 0;
  2424. const int endian = 1;
  2425. if(*(uint8_t*)&endian == 1)
  2426. {
  2427. // Little endian machine
  2428. // Write 8 bytes to store the number of bits in the array
  2429. bytes_written += fwrite(&bitarr->num_of_bits, 1, 8, f);
  2430. // Write the array
  2431. bytes_written += fwrite(bitarr->words, 1, num_of_bytes, f);
  2432. }
  2433. else
  2434. {
  2435. // Big endian machine
  2436. uint64_t i, w, whole_words = num_of_bytes/sizeof(word_t);
  2437. uint64_t rem_bytes = num_of_bytes - whole_words*sizeof(word_t);
  2438. uint64_t n_bits = byteswap64(bitarr->num_of_bits);
  2439. // Write 8 bytes to store the number of bits in the array
  2440. bytes_written += fwrite(&n_bits, 1, 8, f);
  2441. // Write the array
  2442. for(i = 0; i < whole_words; i++) {
  2443. w = byteswap64(bitarr->words[i]);
  2444. bytes_written += fwrite(&w, 1, 8, f);
  2445. }
  2446. if(rem_bytes > 0) {
  2447. w = byteswap64(bitarr->words[whole_words]);
  2448. bytes_written += fwrite(&w, 1, rem_bytes, f);
  2449. }
  2450. }
  2451. return bytes_written;
  2452. }
  2453. // Load a uint64 from little endian format.
  2454. // Works for both big and little endian architectures
  2455. static inline uint64_t le64_to_cpu(const uint8_t *x)
  2456. {
  2457. return (((uint64_t)(x[0])) | ((uint64_t)(x[1]) << 8) |
  2458. ((uint64_t)(x[2]) << 16) | ((uint64_t)(x[3]) << 24) |
  2459. ((uint64_t)(x[4]) << 32) | ((uint64_t)(x[5]) << 40) |
  2460. ((uint64_t)(x[6]) << 48) | ((uint64_t)(x[7]) << 56));
  2461. }
  2462. // Reads bit array from a file. bitarr is resized and filled.
  2463. // Returns 1 on success, 0 on failure
  2464. char bit_array_load(BIT_ARRAY* bitarr, FILE* f)
  2465. {
  2466. // Read in number of bits, return 0 if we can't read in
  2467. bit_index_t num_bits;
  2468. if(fread(&num_bits, 1, 8, f) != 8) return 0;
  2469. num_bits = le64_to_cpu((uint8_t*)&num_bits);
  2470. // Resize
  2471. bit_array_resize_critical(bitarr, num_bits);
  2472. // Have to calculate how many bytes are needed for the file
  2473. // (Note: this may be different from num_of_words * sizeof(word_t))
  2474. bit_index_t num_of_bytes = roundup_bits2bytes(bitarr->num_of_bits);
  2475. if(fread(bitarr->words, 1, num_of_bytes, f) != num_of_bytes) return 0;
  2476. // Fix endianness
  2477. word_addr_t i;
  2478. for(i = 0; i < bitarr->num_of_words; i++)
  2479. bitarr->words[i] = le64_to_cpu((uint8_t*)&bitarr->words[i]);
  2480. // Mask top word
  2481. _mask_top_word(bitarr);
  2482. DEBUG_VALIDATE(bitarr);
  2483. return 1;
  2484. }
  2485. //
  2486. // Hash function
  2487. //
  2488. /* From: lookup3.c, by Bob Jenkins, May 2006, Public Domain. */
  2489. #define hashsize(n) ((uint32_t)1<<(n))
  2490. #define hashmask(n) (hashsize(n)-1)
  2491. #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
  2492. /* From: lookup3.c, by Bob Jenkins, May 2006, Public Domain. */
  2493. #define mix(a,b,c) \
  2494. { \
  2495. a -= c; a ^= rot(c, 4); c += b; \
  2496. b -= a; b ^= rot(a, 6); a += c; \
  2497. c -= b; c ^= rot(b, 8); b += a; \
  2498. a -= c; a ^= rot(c,16); c += b; \
  2499. b -= a; b ^= rot(a,19); a += c; \
  2500. c -= b; c ^= rot(b, 4); b += a; \
  2501. }
  2502. /* From: lookup3.c, by Bob Jenkins, May 2006, Public Domain. */
  2503. #define final(a,b,c) \
  2504. { \
  2505. c ^= b; c -= rot(b,14); \
  2506. a ^= c; a -= rot(c,11); \
  2507. b ^= a; b -= rot(a,25); \
  2508. c ^= b; c -= rot(b,16); \
  2509. a ^= c; a -= rot(c,4); \
  2510. b ^= a; b -= rot(a,14); \
  2511. c ^= b; c -= rot(b,24); \
  2512. }
  2513. /*
  2514. From: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  2515. --------------------------------------------------------------------
  2516. hashword2() -- same as hashword(), but take two seeds and return two
  2517. 32-bit values. pc and pb must both be nonnull, and *pc and *pb must
  2518. both be initialized with seeds. If you pass in (*pb)==0, the output
  2519. (*pc) will be the same as the return value from hashword().
  2520. --------------------------------------------------------------------
  2521. */
  2522. static void hashword2 (
  2523. const uint32_t *k, /* the key, an array of uint32_t values */
  2524. size_t length, /* the length of the key, in uint32_ts */
  2525. uint32_t *pc, /* IN: seed OUT: primary hash value */
  2526. uint32_t *pb) /* IN: more seed OUT: secondary hash value */
  2527. {
  2528. uint32_t a,b,c;
  2529. /* Set up the internal state */
  2530. a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
  2531. c += *pb;
  2532. /*------------------------------------------------- handle most of the key */
  2533. while (length > 3)
  2534. {
  2535. a += k[0];
  2536. b += k[1];
  2537. c += k[2];
  2538. mix(a,b,c);
  2539. length -= 3;
  2540. k += 3;
  2541. }
  2542. /*------------------------------------------- handle the last 3 uint32_t's */
  2543. switch(length) /* all the case statements fall through */
  2544. {
  2545. case 3 : c+=k[2];
  2546. case 2 : b+=k[1];
  2547. case 1 : a+=k[0];
  2548. final(a,b,c);
  2549. case 0: /* case 0: nothing left to add */
  2550. break;
  2551. }
  2552. /*------------------------------------------------------ report the result */
  2553. *pc=c; *pb=b;
  2554. }
  2555. // Pass seed as 0 on first call, pass previous hash value if rehashing due
  2556. // to a collision
  2557. // Using bob jenkins hash lookup3
  2558. uint64_t bit_array_hash(const BIT_ARRAY* bitarr, uint64_t seed)
  2559. {
  2560. uint32_t seed32[2];
  2561. memcpy(seed32, &seed, sizeof(uint32_t)*2);
  2562. // Round up length to number 32bit words
  2563. hashword2((uint32_t*)bitarr->words, (bitarr->num_of_bits + 31) / 32,
  2564. &seed32[0], &seed32[1]);
  2565. // XOR with array length. This ensures arrays with different length but same
  2566. // contents have different hash values
  2567. seed ^= bitarr->num_of_bits;
  2568. return seed;
  2569. }
  2570. //
  2571. // Generally useful functions
  2572. //
  2573. // Generalised 'binary to string' function
  2574. // Adds bits to the string in order of lsb to msb
  2575. // e.g. 0b11010 (26 in decimal) would come out as "01011"
  2576. char* bit_array_word2str(const void *ptr, size_t num_of_bits, char *str)
  2577. {
  2578. const uint8_t* d = (const uint8_t*)ptr;
  2579. size_t i;
  2580. for(i = 0; i < num_of_bits; i++)
  2581. {
  2582. uint8_t bit = (d[i/8] >> (i % 8)) & 0x1;
  2583. str[i] = bit ? '1' : '0';
  2584. }
  2585. str[num_of_bits] = '\0';
  2586. return str;
  2587. }
  2588. char* bit_array_word2str_rev(const void *ptr, size_t num_of_bits, char *str)
  2589. {
  2590. const uint8_t* d = (const uint8_t*)ptr;
  2591. size_t i;
  2592. for(i = 0; i < num_of_bits; i++)
  2593. {
  2594. uint8_t bit = (d[i/8] >> (i % 8)) & 0x1;
  2595. str[num_of_bits-1-i] = bit ? '1' : '0';
  2596. }
  2597. str[num_of_bits] = '\0';
  2598. return str;
  2599. }