PLUGIN bit
lang: "C++"
version: "1.0.1"
date: "2023-03-13"
author: "Julien BRUGUIER"
maintainer: "Julien BRUGUIER <projet.svm@pappy.tf>"
synopsis: "An implementation of bit sets for SVM."
description:
%{
This plugin enables bit set manipulation.
.P
It also allows conversion from strings and to strings.
%}
changelog:
%{
svm-plugin-bit (1.0.1) UNRELEASED; urgency=medium

  * Build for SVM API 2.9.

 -- Julien Bruguier <projet.svm@pappy.tf>  Sun, 01 Mar 2026 22:58:15 +0100

svm-plugin-bit (1.0.0) UNRELEASED; urgency=medium

  * First release of this plugin

 -- Julien Bruguier <projet.svm@pappy.tf>  Fri, 23 May 2025 10:30:23 +0200
%}

example: "Prime numbers"
%{
.nf
#!===SVMBIN===
LOG
PLUGIN "svmcom.so"
PLUGIN "svmint.so"
PLUGIN "===PLUGINLIB==="
ARGUMENT INT nb
PROCESS "prime"
        CODE "main" INLINE
                :memory bit.set/acc, bit.set/m, INT/i, INT/stop
                :bit.set @&nb -> &acc
                :bit.set @&nb -> &m
                2 -> &i
        :label main_loop
                :call set_m P
                :bit.any @&acc @&m -> &acc
                :shift &i
                :int.mul @&i @&i -> &stop
                :goto main_loop :when @&stop IN &0*@&nb
                :bit.not @&acc -> &acc
                :bit.modify @&acc 0 FALSE
                :bit.modify @&acc 1 FALSE
                :memory PTR/p
                :bit.index @&acc -> &p
                0 -> &i
        :label display
                :com.message @(@&p/@&i)
                :shift &i
                :goto display :when @&i IN @&p
                :shutdown
        :label set_m
                :memory BLN*@&i/t, INT/j
                0 -> &j
        :label loop_set_m
                FALSE -> (t/@&j)
                :shift &j
                :goto loop_set_m :when @&j IN t
                TRUE -> ((&t+@&i)-1)
                :bit.pattern @&m t
                :int.mul @&i @&i -> &j
                :bit.shift @&m @&j -> &m
                :return
        END
        MEMORY nb
END
.fi
%}

includes:
%{
#include <vector>
#include <string>
%}

DEFINE

TYPE bit.set
%{
	size_t _size;
	std::vector<unsigned char> _bits;
	type_set(const size_t s)
	:_size(s), _bits(s/8+((s%8)?1:0),'\000') {}
	type_set(const type_set& s)
	:_size(s._size),_bits(s._bits) {}
	explicit type_set(const std::string& s)
	:_size(s.size()*8),_bits(s.begin(),s.end()) {}
	std::string format(const std::string& no, const std::string& yes, const size_t block, const std::string& separator) const
	{
		std::string s;
		for(size_t i=0 ; i<_size ; ++i)
		{
			if((block>0) and ((_size-i)%block==0) and (i>0) and (i<(_size-1)))
			{
				s.push_back(separator[0]);
			}
			if(_bits[i/8] bitand (1<<(7-i%8)))
			{
				s.push_back(yes[0]);
			}
			else
			{
				s.push_back(no[0]);
			}
		}
		return s;
	}
	operator std::string () const
	{
		return format(".","X",8," ");
	}
	std::string string() const
	{
		std::string s;
		for(const auto& c: _bits)
		{
			s.push_back(c);
		}
		return s;
	}
%}
delete default: %{}
copy default: %{}
constant default: %{}
print default: %{}
help:
%{
This type contains a set of bit.
The set has a length fixed at construction time, and supports copy and constant construction.
%}

INTERRUPTION bit.size_mismatch
help:
%{
This interruption is raised when a bit set has an invalid size.
%}

INTERRUPTION bit.out_of_range
help:
%{
This interruption is raised when an index for a bit is outside the set range.
%}

INSTRUCTION bit.set [ INT STR ] : size_or_bits -> bit.set
%{
	SVM_Value value = ::svm_parameter_value_get(svm,argv[0]);
	if(::svm_value_type_is_integer(svm,value))
	{
		auto size = ::svm_value_integer_get(svm,value);
		if(size<0)
		{
			ERROR_INTERNAL(FAILURE,"Invalid size");
		}
		auto set = new type_set(size);
		return NEW_PLUGIN(bit,set,set);
	}
	else
	{
		SVM_String bit = ::svm_value_string_get(svm,value);
		auto set = new type_set(RAW_STRING(bit));
		return NEW_PLUGIN(bit,set,set);
	}
%}
help:
%{
This instruction creates a bit set.
.P
When an integer is specified, the bit set is built with non-set bit with a length described by the integer.
A FAILURE interruption is raised when the size is negative.
.P
When a string is specified, the bit set is built using the string length and the bit are initialised from the string characters.
%}

INSTRUCTION bit.string bit.set -> STR
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	if((set->_size%8)!=0)
	{
		ERROR_EXTERNAL(bit,size_mismatch,"Bit set size is not a multiple of 8.");
	}
	auto s = set->string();
	return NEW_VALUE(string,NEW_STRING(s));
%}
help:
%{
This instruction transforms a bit set into a string, using the bit to initialise the characters.
A bit.size_mismatch interruption is raised when the bit set has a size not being a multiple of 8.
%}

INSTRUCTION bit.format bit.set STR : false STR : true ( INT : block STR : separator ) ? -> STR
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	auto f = ARGV_VALUE(1,string);
	auto t = ARGV_VALUE(2,string);
	if(f.size==0)
	{
		ERROR_INTERNAL(FAILURE,"Empty false string");
	}
	if(t.size==0)
	{
		ERROR_INTERNAL(FAILURE,"Empty true string");
	}
	size_t block = 0;
	std::string separator(" ");
	if(argc>3)
	{
		auto b = ARGV_VALUE(3,integer);
		auto s = ARGV_VALUE(4,string);
		if(b<1)
		{
			ERROR_INTERNAL(FAILURE,"Invalid block size");
		}
		if(s.size==0)
		{
			ERROR_INTERNAL(FAILURE,"Empty separator string");
		}
		block = b;
		separator = RAW_STRING(s);
	}
	std::string s = set->format(RAW_STRING(f),RAW_STRING(t),block,separator);
	return NEW_VALUE(string,NEW_STRING(s));
%}
help:
%{
This instruction builds a text representation of the bit set.
.P
The two first strings shall be non-empty or a FAILURE interruption will be raised.
The first character of the first string is used to represent a non-set bit, and the first character of the second string is used to represent a set bit.
.P
When an integer and an extra string are specified, the integer shall be a positive number or a FAILURE interruption will be raised, and the string shall be non-empty or a FAILURE will also be raised.
When this two extra parameters are specified, the resulting string will show the bit packed in blocks having the integer as size and blocks will be separated by the first character of the string.
%}

INSTRUCTION bit.check bit.set INT : index -> BLN
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	auto index = ARGV_VALUE(1,integer);
	if((index<0) or (index>=set->_size))
	{
		ERROR_EXTERNAL(bit,out_of_range,"Index out of range");
	}
	index = set->_size-index-1;
	unsigned char result = set->_bits[index/8] bitand (1<<(7-index%8));
	return NEW_VALUE(boolean,result?TRUE:FALSE);
%}
help:
%{
This instruction returns the value of a bit as a boolean.
The index shall be within 0 and the size minus 1 or a bit.out_of_range interruption will be raised.
.P
The index 0 is placed on the right of the format representation of the bit set.
%}

INSTRUCTION bit.modify MUTABLE bit.set INT : index [ BLN 'SWAP' ] : value
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	auto index = ARGV_VALUE(1,integer);
	if((index<0) or (index>=set->_size))
	{
		ERROR_EXTERNAL(bit,out_of_range,"Index out of range");
	}
	index = set->_size-index-1;
	unsigned char mask = 1<< (7-index%8);
	if(::svm_parameter_type_is_keyword(svm,argv[2]))
	{
		set->_bits[index/8] ^= mask;
	}
	else
	{
		SVM_Boolean value = ARGV_VALUE(2,boolean);
		if(value==TRUE)
		{
			set->_bits[index/8] |= mask;
		}
		else
		{
			set->_bits[index/8] &= ~mask;
		}
	}
%}
help:
%{
This instruction changes the value of a bit.
The index shall be within 0 and the size minus 1 or a bit.out_of_range interruption will be raised.
The bit can be fixed to a dedicated value by specifying a boolean, or inversed using the SWAP keyword.
.P
The index 0 is placed on the right of the format representation of the bit set.
%}

INSTRUCTION bit.pattern MUTABLE bit.set ( PTR | BLN + )
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	std::vector<bool> pattern;
	SVM_Value v = ::svm_parameter_value_get(svm,argv[1]);
	if(::svm_value_type_is_pointer(svm,v))
	{
		SVM_Address a = ::svm_value_pointer_get_address(svm,v);
		SVM_Size s = ::svm_value_pointer_get_size(svm,v);
		if(s==0)
		{
			ERROR_INTERNAL(FAILURE,"Invalid pattern size");
		}
		for(SVM_Address it=a ; it<(a+s) ; ++it)
		{
			SVM_Value_Boolean b = ::svm_memory_read_address_type_internal(svm,CURRENT(kernel),it,BOOLEAN);
			pattern.push_back(::svm_value_boolean_get(svm,b)==TRUE);
		}
	}
	else
	{
		for(SVM_Index i=1 ; i<argc ; ++i)
		{
			pattern.push_back(ARGV_VALUE(i,boolean)==TRUE);
		}
	}
	size_t p = pattern.size()-1;
	for(size_t i=0 ; i<set->_size ; ++i)
	{
		auto index = set->_size-i-1;
		unsigned char mask = 1<< (7-index%8);
		if(pattern[p])
		{
			set->_bits[index/8] |= mask;
		}
		else
		{
			set->_bits[index/8] &= ~mask;
		}
		if(p==0)
		{
			p = pattern.size()-1;
		}
		else
		{
			--p;
		}
	}
%}
help:
%{
This instruction fills the bit set with a repeated pattern.
.P
The pattern can be provided as a list of booleans, or a pointer towards at least two booleans.
.P
The pattern is applied with the last boolean of the pattern at the index 0 of the set, then the one before of the pattern at the index 1, etc...
.P
As an example:
.nf
	:memory bit.set/set, STR/result
	:bit.set 18 -> &set
	:bit.pattern @&set FALSE FALSE TRUE FALSE
	:bit.format @&set "." "X" 8 " " -> &result
.fi
will produce the string:
.nf
	"X. ..X...X. ..X...X."
.fi
%}

INSTRUCTION bit.size bit.set -> INT
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	return NEW_VALUE(integer,set->_size);
%}
help:
%{
This instruction returns the number of bits of a set.
%}

INSTRUCTION bit.count bit.set -> INT
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	size_t nb=0;
	for(size_t i=0 ; i<set->_size ; ++i)
	{
		auto index = set->_size-i-1;
		unsigned char mask = 1<< (7-index%8);
		if(set->_bits[index/8] bitand mask)
		{
			++nb;
		}
	}
	return NEW_VALUE(integer,nb);
%}
help:
%{
This instruction returns the number of activated bits of a set.
%}

INSTRUCTION bit.empty bit.set -> BLN
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	size_t nb=0;
	for(size_t i=0 ; i<set->_size ; ++i)
	{
		auto index = set->_size-i-1;
		unsigned char mask = 1<< (7-index%8);
		if(set->_bits[index/8] bitand mask)
		{
			++nb;
		}
	}
	return NEW_VALUE(boolean,(nb==0)?TRUE:FALSE);
%}
help:
%{
This instruction returns TRUE when the set has no activated bit in the set, and FALSE otherwise.
%}

INSTRUCTION bit.index bit.set -> PTR
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	std::vector<size_t> positions;
	for(size_t i=0 ; i<set->_size ; ++i)
	{
		auto index = set->_size-i-1;
		unsigned char mask = 1<< (7-index%8);
		if(set->_bits[index/8] bitand mask)
		{
			positions.push_back(i);
		}
	}
	SVM_Memory_Zone zone = ::svm_memory_zone_new(svm);
	::svm_memory_zone_append_internal__raw(svm,zone,INTEGER,positions.size());
	SVM_Value_Pointer p = ::svm_memory_allocate(svm,CURRENT(kernel),zone);
	SVM_Address a = ::svm_value_pointer_get_address(svm,p);
	SVM_Size s = ::svm_value_pointer_get_size(svm,p);
	auto itp = positions.begin();
	for(SVM_Address it=a ; it<(a+s) ; ++it)
	{
		::svm_memory_write_address(svm,CURRENT(kernel),it,::svm_value_integer_new(svm,*(itp++)));
	}
	return p;
%}
help:
%{
This instruction returns a pointer to an allocated memory zone containing integers.
.P
Each integer is the index of an activated bit within the bit set.
%}

INSTRUCTION bit.shift bit.set INT : shift -> bit.set
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	auto shift = ARGV_VALUE(1,integer);
	std::vector<size_t> yes;
	for(size_t i=0 ; i<set->_size ; ++i)
	{
		auto index = set->_size-i-1;
		unsigned char mask = 1<< (7-index%8);
		if(set->_bits[index/8] bitand mask)
		{
			if(((i+shift)>=0) and ((i+shift)<set->_size))
			{
				yes.push_back(i+shift);
			}
		}
	}
	auto result = new type_set(set->_size);
	for(const auto& y: yes)
	{
		auto index = result->_size-y-1;
		unsigned char mask = 1<< (7-index%8);
		result->_bits[index/8] |= mask;
	}
	return NEW_PLUGIN(bit,set,result);
%}
help:
%{
This instruction builds a bit set having the same size of the given bit set, with activated bits shifted.
The shift value is specfied with the integer.
.P
A positive shift value will increase the index of activated bits, and a negative shift value will decrease them.
Activated bits going outside the new bit set are lost.
%}

INSTRUCTION bit.rotate bit.set INT : shift -> bit.set
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	auto shift = ARGV_VALUE(1,integer);
	std::vector<size_t> yes;
	for(size_t i=0 ; i<set->_size ; ++i)
	{
		auto index = set->_size-i-1;
		unsigned char mask = 1<< (7-index%8);
		if(set->_bits[index/8] bitand mask)
		{
			auto n = (i+shift)%set->_size;
			if(n<0) { n += set->_size; }
			yes.push_back(n);
		}
	}
	auto result = new type_set(set->_size);
	for(const auto& y: yes)
	{
		auto index = result->_size-y-1;
		unsigned char mask = 1<< (7-index%8);
		result->_bits[index/8] |= mask;
	}
	return NEW_PLUGIN(bit,set,result);
%}
help:
%{
This instruction builds a bit set having the same size of the given bit set, with activated bits shifted.
The shift value is specfied with the integer.
.P
A positive shift value will increase the index of activated bits, and a negative shift value will decrease them.
Activated bits going outside the new bit set are wrapped to the other side of the bit set.
%}

INSTRUCTION bit.not bit.set -> bit.set
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	auto result = new type_set(*set);
	for(size_t c=0 ; c<result->_bits.size() ; ++c)
	{
		result->_bits[c] = ~result->_bits[c];
	}
	
	return NEW_PLUGIN(bit,set,result);
%}
help:
%{
This instruction creates a bit set containing the inversed bits of the given bit set.
%}

INSTRUCTION bit.all bit.set bit.set + -> bit.set
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	auto result = new type_set(*set);
	for(SVM_Index i=1 ; i<argc ; ++i)
	{
		auto s = ARGV_PLUGIN(i,bit,set);
		if(s->_size!=result->_size)
		{
			ERROR_EXTERNAL(bit,size_mismatch,"Incompatible sizes between sets.");
		}
		for(size_t c=0 ; c<result->_bits.size() ; ++c)
		{
			result->_bits[c] &= s->_bits[c];
		}
	}
	return NEW_PLUGIN(bit,set,result);
%}
help:
%{
This instruction creates a bit set containing the logical and of bits of the given bit sets.
The operation is executed between bits at the same index.
.P
The interruption bit.size_mismatch is raised if at least bit set has not the same size as other sets.
%}

INSTRUCTION bit.any bit.set bit.set + -> bit.set
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	auto result = new type_set(*set);
	for(SVM_Index i=1 ; i<argc ; ++i)
	{
		auto s = ARGV_PLUGIN(i,bit,set);
		if(s->_size!=result->_size)
		{
			ERROR_EXTERNAL(bit,size_mismatch,"Incompatible sizes between sets.");
		}
		for(size_t c=0 ; c<result->_bits.size() ; ++c)
		{
			result->_bits[c] |= s->_bits[c];
		}
	}
	return NEW_PLUGIN(bit,set,result);
%}
help:
%{
This instruction creates a bit set containing the logical or of bits of the given bit sets.
The operation is executed between bits at the same index.
.P
The interruption bit.size_mismatch is raised if at least bit set has not the same size as other sets.
%}

INSTRUCTION bit.operation [ = <> < <= > => ] : operation INT : threshold ( PTR | bit.set bit.set + ) -> bit.set
%{
	auto operation = ARGV_MARKER(0);
	auto threshold = ARGV_VALUE(1,integer);
	std::vector<type_set*> sets;
	SVM_Value v = ::svm_parameter_value_get(svm,argv[2]);
	if(::svm_value_type_is_pointer(svm,v))
	{
		SVM_Address a = ::svm_value_pointer_get_address(svm,v);
		SVM_Size s = ::svm_value_pointer_get_size(svm,v);
		if(s<2)
		{
			ERROR_INTERNAL(FAILURE,"Invalid pointer size");
		}
		for(SVM_Address it=a ; it<(a+s) ; ++it)
		{
			SVM_Value_Plugin s = ::svm_memory_read_address_type_external(svm,CURRENT(kernel),it,CONST_PEP(bit,set));
			sets.push_back(reinterpret_cast<type_set*>(::svm_value_plugin_get_internal(svm,s)));
		}
	}
	else
	{
		for(SVM_Index s = 2 ; s<argc ; ++s)
		{
			sets.push_back(ARGV_PLUGIN(s,bit,set));
		}
	}
	size_t size = sets.front()->_size;
	for(const auto& s: sets)
	{
		if(s->_size!=size)
		{
			ERROR_EXTERNAL(bit,size_mismatch,"Incompatible sizes between sets.");
		}
	}
	std::vector<size_t> counters(size,0);
	for(const auto& s: sets)
	{
		for(size_t i=0 ; i<s->_size ; ++i)
		{
			auto index = s->_size-i-1;
			unsigned char mask = 1<< (7-index%8);
			counters[i] += (s->_bits[index/8] bitand mask)?1:0;
		}
	}
	auto result = new type_set(size);
	auto it=counters.begin();
	for(size_t i=0 ; i<result->_size ; ++i)
	{
		size_t value = *(it++);
		auto index = result->_size-i-1;
		unsigned char mask = 1<< (7-index%8);
		bool r = false;
		if(operation=="=")
		{
			r = value==threshold;
		}
		else if(operation=="<>")
		{
			r = value!=threshold;
		}
		else if(operation=="<=")
		{
			r = value<=threshold;
		}
		else if(operation=="<")
		{
			r = value<threshold;
		}
		else if(operation=="=>")
		{
			r = value>=threshold;
		}
		else if(operation==">")
		{
			r = value>threshold;
		}
		if(r)
		{
			result->_bits[index/8] |= mask;
		}
		else
		{
			result->_bits[index/8] &= ~mask;
		}
	}
	return NEW_PLUGIN(bit,set,result);
%}
help:
%{
This instruction performs a generic boolean operation on each bit of the bit sets, specified either by a pointer towards an array of bit sets or by the explicit list.
When the pointer has a size below 2, a FAILURE interruption is raised.
When a bit set has a different size as other, a bit.size_mismatch interruption is raised.
.P
When bit sets are correct, the instruction counts among all bit sets the number of activated bits for each index, and apply the condition specified by the two first arguments.
When the result is true, the bit at the corresponding index is activated into the resulting bit set.
.P
Common operations can be performed with this single instruction:
.nf
	= 0           NOR operation
	= 1           XOR operation
	> 0           OR operation
	= nb of sets  AND operation
	< nb of sets  NAND operation
.fi
For example, this code:
.nf
	:memory bit.set*3/t, bit.set/r, STR/s
	:bit.set 32 -> (t/0)
	:bit.set 32 -> (t/1)
	:bit.set 32 -> (t/2)
	:bit.pattern @(t/0) FALSE TRUE
	:bit.pattern @(t/1) FALSE FALSE TRUE
	:bit.pattern @(t/2) FALSE FALSE FALSE TRUE
	:bit.operation < SIZE t t -> &r
	:bit.format @&r "." "X" 8 " " -> &s
.fi
will produce the string (result of the NAND operation here):
.nf
	"XXXXXXX. XXXXXXXX XXX.XXXX XXXXXXX."
.fi
%}

INSTRUCTION bit.cmp bit.set [ = <> ] bit.set -> BLN
%{
	auto left = ARGV_PLUGIN(0,bit,set);
	auto op = ARGV_MARKER(1);
	auto right = ARGV_PLUGIN(2,bit,set);
	if(left->_size!=right->_size)
	{
		ERROR_EXTERNAL(bit,size_mismatch,"Incompatible sizes between sets.");
	}
	bool equal = true;
	for(size_t i=left->_size ; i>0 ; --i)
	{
		auto index = left->_size-(i-1)-1;
		unsigned char mask = 1<< (7-index%8);
		if(((left->_bits[index/8] bitand mask)>0) != ((right->_bits[index/8] bitand mask)>0))
		{
			equal = false;
			break;
		}
	}
	return NEW_VALUE(boolean,(((op=="=") and equal) or ((op=="<>") and not equal))?TRUE:FALSE);
%}
help:
%{
This instructions compares two bit sets having the same size.
When the bit sets have not the same size, a bit.size_mismatch interruption is raised.
.P
Equality is obtained when the same bits are activated in both bit sets.
%}

FUNCTION bit.map MUTABLE bit.set PEP : function .* : parameters
%{
	auto set = ARGV_PLUGIN(0,bit,set);
	SVM_Value_PluginEntryPoint func = ::svm_parameter_value_get(svm,argv[1]);
	argv[0] = ::svm_parameter_value_new(svm,NEW_NULL_VALUE(integer));
	argv[1] = ::svm_parameter_value_new(svm,NEW_NULL_VALUE(boolean));
	if(not ::svm_plugin_has_function(svm,func,argc,argv,::svm_parameter_value_new(svm,NEW_VALUE(boolean,TRUE))))
	{
		ERROR_INTERNAL(FAILURE,"Invalid function");
	}
	for(size_t i=0 ; i<set->_size ; ++i)
	{
		auto index = set->_size-i-1;
		unsigned char mask = 1<< (7-index%8);
		argv[0] = ::svm_parameter_value_new(svm,NEW_VALUE(integer,i));
		argv[1] = ::svm_parameter_value_new(svm,NEW_VALUE(boolean,((set->_bits[index/8] bitand mask)?TRUE:FALSE)));
		SVM_Value_Boolean b = ::svm_function_call(svm,func,argc,argv);
		if(::svm_value_boolean_get(svm,b))
		{
			set->_bits[index/8] |= mask;
		}
		else
		{
			set->_bits[index/8] &= ~mask;
		}
	}
%}
help:
%{
Please refer to the instruction bit.map.
%}

INSTRUCTION bit.map MUTABLE bit.set PEP : function .* : parameters
%{
	function_map(svm,argc,argv);
%}
help:
%{
This instruction applies a function with extra parameters on a bit set.
.P
The function prototype shall be:
.nf
	FUNCTION <name> INT : index BLN : bit <extra parameters> -> BLN : new_bit
.fi
When the function does not exist, a FAILURE interruption is raised.
.P
The function is called for each bit of the set with the bit index and its value, and the returned value modifies the value of the bit within the bit set. 
%}