tlk00 / bitmagic Goto Github PK

The function should accept the start position i and return pfound == 1 if found, pfound == 0 otherwise.
int BM_bvector_get_first(BM_BVHANDLE h, unsigned int i, unsigned int* pi, int* pfound);

hello, thanks for your great job, BM is powerful !
it seems doesn't free memory completely when calling clear_all(true),but large size of data works well.

do you think that BitMagic could be installed with https://conan.io/ ?

hello,

when i use the example at line 650 of inv_list.cpp to try to deserialize a bvector i have serialized before the flag that correspond to Logical error on i/o operation is raised in the isstream, but the bvector i obtain with it is good and has the same data than the bvector i have serialized before.

Any idea why the flag is raised even if its work?

my current code is :
std::ifstream f(path std::ios::in);
bm::serializer<bm::bvector<> >::buffer sbuf;
bm::bvector<> bv;
unsigned len;
bitVector.read((char*) &len, std::streamsize(sizeof(len)));
sbuf.resize(len, false);
bitVector.read((char*) sbuf.data(), std::streamsize(len));
if(bitVector.fail()){
std::cout<<"error"<<std::endl;
}
bm::deserialize(bv, sbuf.data());
return bv;

Hi,

Thank you for all your work and all the resources you had provided.

Is there any reference to efficiently pack the 2 bits into a larger data type(basically int64)?

A = 0000.........10(64 bit), B = 0000........11(64 bit), C = 0000........01, and so on, these are int64 values containing 2-bit values.

So, I want to pack them in an int64 datatype(32 2-bit values)
Z = 101101...........(int64 value, containing packed values of A, B, C, D, .............. )

I want to perform this efficiently. So It would be helpful if you can help me with some references.

Thanks in advance!

Excerpt of a stack:
#0 0x00000000007d192f in bm::bvector<bm::mem_alloc<bm::block_allocator, bm::ptr_allocator, bm::alloc_pool<bm::block_allocator, bm::ptr_allocator> > >::bit_or (this=0x7ff9d302e060, bv1=..., bv2=...,
opt_mode=bm::bvector<bm::mem_alloc<bm::block_allocator, bm::ptr_allocator, bm::alloc_pool<bm::block_allocator, bm::ptr_allocator> > >::opt_none) at /export/home/satskyse/ns/bld/include/util/bitset/bm.h:4783
#1 0x00000000007cdb71 in bm::operator|<bm::mem_alloc<bm::block_allocator, bm::ptr_allocator, bm::alloc_pool<bm::block_allocator, bm::ptr_allocator> > > (bv1=..., bv2=...)
at /export/home/satskyse/ns/bld/include/util/bitset/bm.h:2397
#2 0x00000000007c6640 in ncbi::CJobStatusTracker::GetOutdatedReadVacantJobs (this=0x3047998, timeout=..., read_jobs=..., gc_registry=...) at /export/home/satskyse/ns/bld/src/app/netschedule/job_status.cpp:423
#3 0x00000000007fa466 in ncbi::CQueue::NotifyListenersPeriodically (this=0x3047970, current_time=...) at /export/home/satskyse/ns/bld/src/app/netschedule/ns_queue.cpp:3103
#4 0x0000000000887b8f in ncbi::CQueueDataBase::NotifyListeners (this=0x3045c10) at /export/home/satskyse/ns/bld/src/app/netschedule/queue_database.cpp:1439
#5 0x00000000008bf1ca in ncbi::CGetJobNotificationThread::x_DoJob (this=0x30510e0) at /export/home/satskyse/ns/bld/src/app/netschedule/ns_notifications.cpp:1006
#6 0x00000000008bec39 in ncbi::CGetJobNotificationThread::Main (this=0x30510e0) at /export/home/satskyse/ns/bld/src/app/netschedule/ns_notifications.cpp:941
#7 0x0000000000c08767 in ncbi::CThread::Wrapper (arg=0x30510e0) at /export/home/satskyse/ns/bld/src/corelib/ncbithr.cpp:572
#8 0x0000000000c0b1fe in ncbi::ThreadWrapperCaller (arg=0x30510e0) at /export/home/satskyse/ns/bld/src/corelib/ncbithr.cpp:668
#9 0x0000000000c09074 in ncbi::ThreadWrapperCallerImpl (arg=0x30510e0) at /export/home/satskyse/ns/bld/src/corelib/ncbithr.cpp:676
#10 0x00007ff9d46f2dd5 in start_thread () from /lib64/libpthread.so.0
#11 0x00007ff9d3b8102d in clone () from /lib64/libc.so.6

Here is the corresponding source code:
421 TNSBitVector candidates;
422
423 candidates = *m_StatusStor[(int) CNetScheduleAPI::eDone] |
424 *m_StatusStor[(int) CNetScheduleAPI::eFailed] |
425 *m_StatusStor[(int) CNetScheduleAPI::eCanceled];

gdb session:
(gdb) l
2392 template
2393 inline bvector operator| (const bvector& bv1,
2394 const bvector& bv2)
2395 {
2396 bvector ret;
2397 ret.bit_or(bv1, bv2, bvector::opt_none);
2398 return ret;
2399 }
2400
2401 //---------------------------------------------------------------------
(gdb) f 0
#0 0x00000000007d192f in bm::bvector<bm::mem_alloc<bm::block_allocator, bm::ptr_allocator, bm::alloc_pool<bm::block_allocator, bm::ptr_allocator> > >::bit_or (this=0x7ff9d302e060, bv1=..., bv2=...,
opt_mode=bm::bvector<bm::mem_alloc<bm::block_allocator, bm::ptr_allocator, bm::alloc_pool<bm::block_allocator, bm::ptr_allocator> > >::opt_none) at /export/home/satskyse/ns/bld/include/util/bitset/bm.h:4783
4783 bm::word_t** blk_blk_arg1 = (i < top_blocks1) ? blk_root_arg1[i] : 0;
(gdb) l
4778 bm::word_t*** blk_root_arg1 = bv1.blockman_.top_blocks_root();
4779 bm::word_t*** blk_root_arg2 = bv2.blockman_.top_blocks_root();
4780
4781 for (unsigned i = 0; i < top_blocks; ++i)
4782 {
4783 bm::word_t** blk_blk_arg1 = (i < top_blocks1) ? blk_root_arg1[i] : 0;
4784 bm::word_t** blk_blk_arg2 = (i < top_blocks2) ? blk_root_arg2[i] : 0;
4785
4786 if (blk_blk_arg1 == blk_blk_arg2)
4787 {
(gdb) p blk_root_arg1
$1 = (bm::word_t ***) 0x0
(gdb) p top_blocks
$2 = 1
(gdb) p i
$3 = 0
(gdb) p top_blocks1
$4 = 1
(gdb) p top_blocks2
$5 = 1
(gdb)
(gdb) p blk_root_arg1
$10 = (bm::word_t ***) 0x0
(gdb) p blk_root_arg2
$11 = (bm::word_t ***) 0x0

Note: GCC 7.3.0 was used

No coredumps, aborts or crashes are allowed under JVM. May be implemented as a platform-specific macro at the compilation stage. Example:

Hi there,

I'm a big fan of BitMagic and we use it in our database for a variety of things. I'm trying to build with Clang for the first time and I'm getting the error 'no member named 'allocate_tempblock' in 'bvector', same goes for 'free_tempblock'. I might be missing something stupid, but I can't actually see those methods being defined directly on the bvector, is there something I need to #define?

Severity Code Description Project File Line Suppression State
Error C3861 '_mm256_extract_epi32': identifier not found bmjni-avx2 \git\bitmagic\src\bmavx2.h 1489

Xcode is warning of this though it's basically impossible to trigger. In this function:

template<class Alloc> 
void 
bvector<Alloc>::combine_operation_with_block(unsigned          nb,
                                             bool              gap,
                                             bm::word_t*       blk,
                                             const bm::word_t* arg_blk,
                                             bool              arg_gap,
                                             bm::operation     opcode)

... the tmp_buf local at the top is not explicitly zero-initialized and Xcode doesn't realize that the goto assign_gap_result will always trigger the if (res_len > threshold) block and return before set_gap_level is called.

Logic error
...vendor/bm/bmfunc.h:2432:43: The left operand of '&' is a garbage value
…: Calling 'bvector::set_range'
...vendor/bm/bm.h:1650:5: Calling 'bvector::set_range_no_check'
...vendor/bm/bm.h:2958:1: Entered call from 'bvector::set_range'
...vendor/bm/bm.h:2980:10: Assuming 'nbit_left' is not equal to 0
...vendor/bm/bm.h:3006:38: Assuming the condition is false
...vendor/bm/bm.h:3010:16: Loop body executed 0 times
...vendor/bm/bm.h:3069:5: Calling 'bvector::combine_operation_with_block'
...vendor/bm/bm.h:2649:1: Entered call from 'bvector::set_range_no_check'
...vendor/bm/bm.h:2715:21: Assuming 'res_len' is <= 'threshold'
...vendor/bm/bm.h:2742:17: Calling 'set_gap_level'
...vendor/bm/bmfunc.h:2429:1: Entered call from 'bvector::combine_operation_with_block'
...vendor/bm/bmfunc.h:2432:43: The left operand of '&' is a garbage value

A possible fix for this would be hoisting the code from the if (res_len > threshold) block into its own function and avoiding the goto.

The separate memory management of JVM and the library leads to the very awkward resource management in the Java code, as each created bitvector needs to be destroyed explicitly. The problem can be mitigated by having a custom implementation of the new and delete methods as outlined in the attached file.
sorensen.pdf

bm/encoding.h:461:24: warning: assigning field to itself [-Wself-assign-field]
used_bits_ ^= used_bits_;

Hello Anatoliy, can I suggest the inclusion of the BitMagic in the vcpkg list?

Hi,

Probably I am missing something obvious, but the term svector_u32 does not appear in any of the header files in BitMagic/src but when I attempt to follow one of your examples it appears as a type. Is the example out of date? If so what is the correct usage?

For completeness here is the example:

            const char* s = "ATGTCNNNNNTATA";
            svector_u32 sv;
            {
                svector_u32::back_insert_iterator bi = sv.get_back_inserter();
                for (unsigned i = 0; s[i]; ++i)
                {
                    bi = DNA2int(s[i]);
                }
                bi.flush();
            }
            sv.optimize(); // this will RLE compress the sparse (N) plane

My goal is to be able to selectively deserialize as well, but that example also makes use of svector_u32.

Thanks

Hello,

I'm trying to package Bit Magic for guix and use it as a dependency for one of my other projects. The in-place build approach seems to work, but the cmake one appears broken with the following output. I would like to use cmake as it is easier to use (from what I know) than using the more custom primary approach.

BitMagic$ mkdir bld
BitMagic$ cd bld/
BitMagic/bld$ cmake ..
-- The C compiler identification is GNU 9.2.1
-- The CXX compiler identification is GNU 9.2.1
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files have been written to: /home/anadon/Documents/code/guix-packages/BitMagic/bld
anadon@goodadvicemallard:~/Documents/code/guix-packages/BitMagic/bld$ ls
CMakeCache.txt  CMakeFiles  cmake_install.cmake  Makefile
anadon@goodadvicemallard:~/Documents/code/guix-packages/BitMagic/bld$ make
/gnu/store/2hxfv110z443qbzal6rwsny4sx13dys3-cmake-3.15.5/bin/cmake -S/home/anadon/Documents/code/guix-packages/BitMagic -B/home/anadon/Documents/code/guix-packages/BitMagic/bld --check-build-system CMakeFiles/Makefile.cmake 0
/gnu/store/2hxfv110z443qbzal6rwsny4sx13dys3-cmake-3.15.5/bin/cmake -E cmake_progress_start /home/anadon/Documents/code/guix-packages/BitMagic/bld/CMakeFiles /home/anadon/Documents/code/guix-packages/BitMagic/bld/CMakeFiles/progress.marks
make -f CMakeFiles/Makefile2 all
make[1]: Entering directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
make -f CMakeFiles/strsvsample03.dir/build.make CMakeFiles/strsvsample03.dir/depend
make[2]: Entering directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
cd /home/anadon/Documents/code/guix-packages/BitMagic/bld && /gnu/store/2hxfv110z443qbzal6rwsny4sx13dys3-cmake-3.15.5/bin/cmake -E cmake_depends "Unix Makefiles" /home/anadon/Documents/code/guix-packages/BitMagic /home/anadon/Documents/code/guix-packages/BitMagic /home/anadon/Documents/code/guix-packages/BitMagic/bld /home/anadon/Documents/code/guix-packages/BitMagic/bld /home/anadon/Documents/code/guix-packages/BitMagic/bld/CMakeFiles/strsvsample03.dir/DependInfo.cmake --color=
Scanning dependencies of target strsvsample03
make[2]: Leaving directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
make -f CMakeFiles/strsvsample03.dir/build.make CMakeFiles/strsvsample03.dir/build
make[2]: Entering directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
[  1%] Building CXX object CMakeFiles/strsvsample03.dir/samples/strsvsample03/strsvsample03.cpp.o
/usr/bin/c++   -I/home/anadon/Documents/code/guix-packages/BitMagic/src  -Wall -Wextra -Wno-ignored-qualifiers -march=core2 -fPIC -march=core2   -std=gnu++11 -o CMakeFiles/strsvsample03.dir/samples/strsvsample03/strsvsample03.cpp.o -c /home/anadon/Documents/code/guix-packages/BitMagic/samples/strsvsample03/strsvsample03.cpp
In file included from /home/anadon/Documents/code/guix-packages/BitMagic/src/bmserial.h:54,
                 from /home/anadon/Documents/code/guix-packages/BitMagic/src/bmsparsevec_serial.h:33,
                 from /home/anadon/Documents/code/guix-packages/BitMagic/samples/strsvsample03/strsvsample03.cpp:43:
/home/anadon/Documents/code/guix-packages/BitMagic/src/bmxor.h: In function ‘bm::id64_t bm::compute_xor_complexity_descr(const word_t*, const word_t*, bm::block_waves_xor_descr&, unsigned int&)’:
/home/anadon/Documents/code/guix-packages/BitMagic/src/bmxor.h:164:56: warning: comparison is always true due to limited range of data type [-Wtype-limits]
  164 |         if ((xor_change <= 1) && (x_descr.sb_change[i] >= 0))
      |                                   ~~~~~~~~~~~~~~~~~~~~~^~~~
[  2%] Linking CXX executable ../build/bin/strsvsample03
/gnu/store/2hxfv110z443qbzal6rwsny4sx13dys3-cmake-3.15.5/bin/cmake -E cmake_link_script CMakeFiles/strsvsample03.dir/link.txt --verbose=1
/usr/bin/c++   -Wall -Wextra -Wno-ignored-qualifiers -march=core2 -fPIC -march=core2   -Wl,-stack_size,0x100000000 -rdynamic CMakeFiles/strsvsample03.dir/samples/strsvsample03/strsvsample03.cpp.o  -o ../build/bin/strsvsample03 
ld: unrecognized -a option `ck_size'
collect2: error: ld returned 1 exit status
make[2]: *** [CMakeFiles/strsvsample03.dir/build.make:87: ../build/bin/strsvsample03] Error 1
make[2]: Leaving directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
make[1]: *** [CMakeFiles/Makefile2:130: CMakeFiles/strsvsample03.dir/all] Error 2
make[1]: Leaving directory '/home/anadon/Documents/code/guix-packages/BitMagic/bld'
make: *** [Makefile:87: all] Error 2

I'm packaging in guix which has specific tooling for projects built with cmake. This requires that CMakeLists.txt have information for handling installation of files. I think I'll be able to submit another pull request adding this.

While running BitCountTest on Linux:
java: /home/kholodov/git/BitMagic/lang-maps/jni/../../src/bm.h:1242: bool bm::bvector<A>::set_bit(bm::id_t, bool) [with Alloc = libbm::mem_alloc<libbm::block_allocator, libbm::ptr_allocator>; bm::id_t = unsigned int]: Assertion `n < size_' failed.

Hi!

Today I published two Rust packages mentioned in #61 to crates.io:
https://crates.io/crates/bitmagic
https://crates.io/crates/bitmagic-sys
(let me know if you want to be added as owner, BTW).

I'm using these packages in sourmash-bio/sourmash#1221, and the detail is that we build Python wheels (the binary format for Python packages) for the manylinux-supported platforms: aarch64, s390x and ppc64le. But, when I tried to build the wheels, compilation failed with errors in

impossible constraint in 'asm':
     asm volatile("cpuid" : "=a" (eax), "=b" (ebx), "=c" (ecx), "=d" (edx) : "a" (1));

I'm adding CI to test in these platforms in https://github.com/luizirber/bitmagic-rs/, and here is a similar error log:
https://github.com/luizirber/bitmagic-rs/pull/2/checks?check_run_id=2153526751#step:4:435

Considering the surrounding code, it is failing due to none of these platforms having SIMD, which makes sense, but... I don't know how to disable these checks in the places I can control externally (cmake defines). Any tips/suggestions on how to achieve that?

Thanks!

P.S: saying "we don't support these platforms" is totally fine too, I kind of started building s390x and ppc64le wheels just because I tested it once and it worked for sourmash at that point. I do know about some ppc64le users, but the benefits we get from bitmagic are way too good and are making me considering dropping them.

Hi,

It appears that there is a bug in the implementation of the flip function (full vector flip). The flipping seems to assume that there is a large tail of zeroes at the end of every bvector and flipping causes that implicit tail to become real.

To reproduce:

#include <iostream>
#include "bm.h"

int main() {
  bm::bvector<> bv;
  bv.set_range(10, 11);
  std::cout << "Count pre flip=" << bv.count() << std::endl;
  bv.flip();
  std::cout << "Count post flip=" << bv.count() << std::endl;
}

The output

Count pre flip=2
Count post flip=4294967293

I would have expected that a flipping operation would not change the size of the vector and the post flip count to be 9.

This also affects other APIs, because the rest of the code now believes there is a big set of 1s at the end of the vector.

When compiling w/-Wconversion:

Error: Implicit conversion loses integer precision: 'unsigned long long' to 'bm::word_t' (aka 'unsigned int')

As the type of bm::word_t is unsigned int (ie: 32-bits on a 32-bit platform), this function could silently truncate the result of the data. I don't actually use this code so I don't have a test-case available to prove it, but it looks like a reasonable warning.

{
#if (BM_UNALIGNED_ACCESS_OK == 1)
	bm::id64_t a = *((bm::id64_t*)buf_);
#else
	bm::word_t a = buf_[0]+
                   ((bm::id64_t)buf_[1] << 8)  +
                   ((bm::id64_t)buf_[2] << 16) +
                   ((bm::id64_t)buf_[3] << 24) +
                   ((bm::id64_t)buf_[4] << 32) +
                   ((bm::id64_t)buf_[5] << 40) +
                   ((bm::id64_t)buf_[6] << 48) +
                   ((bm::id64_t)buf_[7] << 56);
#endif
    buf_+=sizeof(a);
    return a;
}

I have a weird behavior of a bm::bvector<> that appears from a given size.
The bitvector if full of 1 from 0 to 16.7 million.
I expect that a call to select on bm::bvector<>::rs_index_type to be the identity (x->x)
But this is not the case from a given size of the bitvector.
With 15 million, everything works correctly, but not with 16.7 million.
Interestingly when I plot the calc_stat function I have
Bit-vector statistics: GAP (compressed blocks)=1, BIT (uncompressed blocks)=0
for the 15 million dataset and
Bit-vector statistics: GAP (compressed blocks)=0, BIT (uncompressed blocks)=0
For the 16.7 million

Is this expected?
I tried to use the latest release and the actual codebase for the same result.

Hi, we read your blogpost and are really looking forward to using this lib, but I just want to check if you have any sample projects using bitmagic as a library and have a Cmake based workflow so we can use that to automate the fetching and linking of BitMagic with our project?

Given the particular issues I had, it probably makes sense to add tooling for CI and coverage over supported platforms. Travis, AppVeyor, Coveralls, etc.

Hi, thanks for the great library!

I started two crates for wrapping the C FFI for using in Rust, one is the unsafe low-level bindings (bitmagic-sys) and another a safe/high-level/closer to Rust usage, based on the API of fixedbitset (bitmagic), but I intend to expose more methods over time.

Overall it is already working, after I commented out a line in cmake. The big problem I'm having is that if I run tests with more than 1 thread, the C++ exception emulation with longjmp/setjmp creates memory corruption. I'm looking into that to see what is going on...

I didn't register the crates in crates.io because I wanted to check if you first to see if that's OK, and I would also like to try to use the crate a bit more before registering anyway.

Hello,

It is an amazing project. I was wondering if a Python interface of this library is planned in the short-term.

Warmly,

Roy.

Hi,

First I want to thank you for this awesome library.

I'm experimenting on binary NLP technics and I was wondering if you could publish a bitmagic version of SOM (self organizing map) using about ~ 10 millions of extremely sparse (< 5 / 100 000) binary vectors of same size ~ 1Mbits. The map could be for instance 128 x 128 locations.

It could be a huge step froward for me to see a correct use of bitmagic on this particular subject.

Thanks for your help.

for
bm::set2set_11_transform::run()

the first argument should be able to be const