Hi,
I had a similar frustration a year ago, and I made a native functor to solve my problem. It didn't make it into the standard library.
It's available at:
You can import it using ozmake like this:
Then, in the OPI you can do: (just copy and past this, don't change anything, I mean DON'T try to be smart and replace .so{native} by the actual extension on your machine!)
declare [BV] = {Link ['x-ozlib://spiessens/base/bitvector.so{native}']} {Wait BV} {Inspect BV}
You will see the bit operations.
Mind you, test what you want to use, because it may be buggy. For instance BV.hamdist does not seem to do a proper job, and bitsOn, scan0 and scan1 may be buggy too. The and/or/xor/not/shift operations have been thoroughly tested though
The module is based on gmp's large integers, and provides the bit-operations gmp provides, basically.
I didn't provide much documentation though, only this:
A library of bit operations implemented on top of the gmp (Gnu Multi Precision) library. For reasons of efficiency, the bit operations [clrbit, setbit, and, 'or', xor, not, set] update the state of the first argument. Only BitVector.new creates a new BitVector and returns it. Array-like dot operations are provided in the following way: X.N provides the Nth bit of BitVector X. X.N:=Y sets the Nth bit of X to Y provided Y is equal to 0 or 1, and if used as a function will return the value of X.N before the assignment.
The nice thing is that the second operator can simply be an integer (or a BitVector) Note that BitVectors have infinite length (conceptually) a series of infinitely many 1's is presented as: -1 (~1 in O z notation) a series of infinitely many 0's is presented as: 0 Keep in mind that most of the bit operations are NOT functions: they change their first argument.
here's a small demo:
declare [BV] = {Link ['x-ozlib://spiessens/base/bitvector.so{native}']} {Wait BV} {Inspect BV} X = {BV.new 123456789} %creates new BitVector X Y = {BV.new 0} {Inspect {String.toAtom {BV.toString X 36}}} {Inspect {String.toAtom {BV.toString X 10}}} {Inspect {String.toAtom {BV.toString X 2}}}
{BV.'or' X 0b110110110110} %updates X .. mind you: .'or' instead of simply .or because or is Oz keyword {Inspect {String.toAtom {BV.toString X 36}}}
{BV.'not' X} %updates X ... same remark, not is Oz keyword {Inspect {String.toAtom {BV.toString X 36}}} {Inspect {String.toAtom {BV.toString X 36}}}
{BV.'not' Y} %updates Y {Inspect {String.toAtom {BV.toString Y 2}}} {Inspect Y.20} Y.20:=0 {Inspect Y.20} {Inspect {String.toAtom {BV.toString Y 2}}} {BV.and X Y} %updates X {Inspect {String.toAtom {BV.toString X 36}}} {Inspect {String.toAtom {BV.toString X 36}}} {Inspect {String.toAtom {BV.toString X 36}}}
If you have questions, bugreports, or special requests, just ask me.
Enjoy, Fred.
On 21 May 2006, at 05:44, Sukit Tretriluxana wrote: Hi Anthony,
I really appreciate your time in explaining this to me. Definitely what you have provided really helps. Most importantly, it confirms my understanding that Oz really doesn't have built-in bit-wise operations. After thinking about it for a while, according to my understanding, it kind of makes sense since an integer in Oz is defined as a pretty high level abstraction. It is portable accross hardward and can grow automatically as much as it needs to be. Having the bit-wise operation would perhaps raise a number of questions and issues of how to do that without sacrificing the abstraction.
Anyhow, I was hoping, before getting your response, that the standard library might have something already to make this a little bit easier. Apparently, this is unfortunately not the case.
Ed
On 5/20/06, Anthony Borla <[EMAIL PROTECTED]> wrote: "Sukit Tretriluxana" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Could someone please shed some light how I can perform
> bit operations on integers? Basically, I am getting a series of
> bytes that represent an integer number. This number in turn
> actually represent a bit pattern that determines whether
> something on or off. I want to be able to check say if if
> bit 13, for example, is on or off.
>
I was actually asking myself similar questions last week [well, more about
bit shifting / rotating], and after a little exploration of this issue I
*think* I can answer your question [I'll try to, anyway :)].
As you've already found out Oz does not implement the usual crop of C-like
bitwise operations [i.e. left-shift, right-shift etc] on integer or
integer-related types. Instead it offers facilities, specifically the:
* BitString
* BitArray
types, which may be used to effect such tasks. Put another way, you can't
just simply code up [ala C] the following:
IntegerValue >> 4
or:
IntegerValue & Mask
but must take a more indirect route involving the earlier-mentioned types.
Both types offer roughly similar bit manipulation capability in that you
can:
* Test whether individual bits are set ['test' in 'BitArray', 'get' in
'BitString']
* Set and clear specified bits ['set' and 'clear' in 'BitArray', 'put'
in 'BitString']
* Perform the bitwise Boolean operations, AND ['conj'] and OR
['disj']
* Extract a list of the indexes set to 1 [At first I thought this was
a rather odd feature (as compared to a list of all bits), but later
found that it not only offers a very compact representation of
the bit data, but also makes implementing bit shifting a trivial
task - pretty neat, after all !]
For my purposes I found 'BitString' more useful primarily because you can
initialise it with a specified bit value [via a list of indexes] something
that doesn't appear possible with 'BitArray' [you have to 'set' each bit, a
rather painful exercise I should think !].
Anyway, I'm sure a couple of your questions have already been answered,
albeit indirectly, but I'll now address some specifics. Assuming you've
built a 8 bit 'BitString' instance:
BS = {BitString.make [2 3 5]}
testing to see whether bit 3 [using a zero-based index scheme] is as simple
as:
% Is bit 3 set ?
if {BitString.get BS 3}then
...
As for building a 'BitString' representation of an 'integer' out of a series
of 'bytes' it really is simply a matter of appropriately joining these
entities together as a list [being mindful of endianness, that is, whether
byte zero starts on the left side or the right side of the 'integer'], and
converting this list to a list of indexes of bits to be set. The routines,
'IntToBitString' and 'MakeIndexList', in the code below illustrate one
approach [hopefully a reasonably efficient one !] to this task.
Finally, I hope this response is of help to you. I've been exploring the Oz
language [in far too short time bursts !] for a number of months now, and
have really enjoyed doing so. While I have found it relatively easy to use,
expressive, and ideal for building simple abstractions [like the example
below] it does require that you let go of some preconceived notions [like
assumptions about bit manipulation :)] in order to facilitate learning.
Cheers,
Anthony Borla
Some sample code appears below. Be warned, it is woefully incomplete, and
not thoroughly tested, but hopefully enough to illustrate some basic ideas
about Oz bit manipulations and simple abstraction building.
functor
import
System(show showInfo print printInfo) Application(exit)
define
fun {NewInteger Value}
local
%% Helpers
fun {I2BS I Bin}
if I =< 0 then
Bin
else D = I div 2 M = I mod 2 in
{I2BS D (M + &0)|Bin}
end
end
fun {I2BL I Bin}
if I =< 0 then
Bin
else D = I div 2 M = I mod 2 in
{I2BL D M|Bin}
end
end
fun {BL2I Bin}
P = fun {$ X Y} Y + {Number.pow 2 X} end
in
{List.foldR Bin P 0}
end
fun {MakeIndexList L AC}
case L of nil then nil
elseof H|T then
if H == 1 then
AC|{MakeIndexList T (AC + 1)}
else
{MakeIndexList T (AC + 1)}
end
end
end
fun {IntToBitString I}
{BitString.make 32 {MakeIndexList {List.reverse {I2BL I ""}} 0}}
end
fun {BitStringToInt Bin}
{BL2I {BitString.toList Bin}}
end
fun {BitListToInt Bin}
{BL2I Bin}
end
fun {IntToBinaryString I}
{I2BS I ""}
end
fun {BinaryStringToInt Bin}
P = fun {$ I X Y} Y + (X - 48) * { Number.pow 2 (I - 1)} end
in
{List.foldRInd {List.reverse Bin} P 0}
end
%% Private Data
Integer = {NewCell Value}
IBS = {NewCell {IntToBitString Value}}
in
%% Interface
fun {GetValue}
[EMAIL PROTECTED]
end
proc {SetValue I}
Integer := I
IBS := {IntToBitString I}
end
fun {AsBitString}
[EMAIL PROTECTED]
end
fun {AsBinaryString}
{IntToBinaryString @Integer}
end
fun {Shift N}
P = fun {$ X} X + N end
Q = fun {$ X} X >= 0 end
in
if N == 0 then
% Clone current
{NewInteger @Integer}
elseif N > 0 then
% Right Shift
{NewInteger {BitListToInt {List.map {BitString.toList @IBS} P}}}
else
% Left Shift
{NewInteger {BitListToInt {List.filter {List.map {BitString.toList
@IBS} P} Q}}}
end
end
%% ... incomplete ...
fun {Rotate N}
[EMAIL PROTECTED]
end
fun {AND I}
[EMAIL PROTECTED]
end
fun {OR I}
[EMAIL PROTECTED]
end
fun {XOR I}
[EMAIL PROTECTED]
end
fun {NEG I}
[EMAIL PROTECTED]
end
fun {CMPL2 I}
[EMAIL PROTECTED]
end
end
in
ops(getValue:GetValue setValue:SetValue asBitString:AsBitString
asBinaryString:AsBinaryString shift:Shift rotate:Rotate
bitAND:AND bitOR:OR bitXOR:XOR neg:NEG cmpl2:CMPL2)
end
%% Quick Demonstration Harness
I
in
I = {NewInteger 5}
{System.show {I.getValue}}
{System.showInfo {IntToString { I.getValue}}}
{System.showInfo {I.asBinaryString}}
{System.showInfo {{I.shift 2}.getValue} }
{I.setValue 20}
{System.showInfo {{I.shift ~1}.getValue} }
{System.show {I.asBitString}}
{Application.exit 0}
end
_________________________________________________________________________________
mozart-users mailing list [email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
_________________________________________________________________________________
|
