OpenEuphoria

2. Re: boolean sequence

• Posted by "Juergen Luethje" <j.lue at gmx.de> Sep 02, 2004
• 442 views

Tone =A6koda wrote:

> in C++ if you have an array of 100 boolean (0 or 1) values it will take
> only 100 bits (the C++ "bitset" class exists), in euphoria same array
> will take 32*100bits, 32x more memory. so if you have very large array,
> there is big difference between 1 MB and 32 MB. 1 MB will quickly
> allocate, 32 MB will take long to allocate.
>
> does in euphoria exist any such library? similar library could exist
> for array with char types (8bit) (0-255 numbers), and array with short
> types (16bit) (0 to 65,535 numbers).
>
> i want such library to save memory and also maybe speed.

In the Euphoria archieves, there is my library "bit.zip".
Besides other routines, it contains 5 functions that let you
treat 32-bit integers as "bit arrays". Short descriptions:

- x = bit_set(x, number)
  Set the bit in 'x', that is indexed by 'number', to 1.

- x = bit_reset(x, number)
  Set the bit in 'x', that is indexed by 'number', to 0.

- i = bit_test(x, number)
  Return the value (0 or 1) of the bit in 'x', that is
  indexed by 'number'.

- i = bit_scan_forward(x)
  Return the number of the lowest order bit in 'x', that is
  set (or return -1, if x = 0).

- i = bit_scan_reverse(x)
  Return the number of the highest order bit in 'x', that is
  set (or return -1, if x = 0).

All these functions are fast, because they are internally
implemented in ASM.

Regards,
   Juergen

--=20
A: Because it considerably reduces the readability of the text.
Q: Why?
A: Top posting.
Q: What is annoying in e-mail and news?

4. Re: boolean sequence

• Posted by Pete Lomax <petelomax at blueyonder.co.uk> Sep 02, 2004
• 474 views

On Thu, 02 Sep 2004 08:58:10 -0700, Tone =8Akoda
<guest at RapidEuphoria.com> wrote:




>array, there is big difference between 1 MB and 32 MB.
OK, I agree on that point.
>1 MB will quickly allocate, 32 MB will take long to allocate.
But I'm not sure I agree on that point.
If you are only allocating it once, the (time) difference is
negligible.
If you intend to resize it frequently, as far as I can tell RDS EU is
pretty fast, and I seriously doubt you would see any gain.

Do you intend to resize or not?
Would it not be better to create a dll from your C++ code and write a
Euphoria wrapper for it?

Regards,
Pete

6. Re: boolean sequence

• Posted by Tone Škoda <tskoda at email.si> Sep 02, 2004
• 452 views

yes i already looked at your lib and exactly those functions you mentioned. i
will make a wrapper lib out of it then.

8. Re: boolean sequence

• Posted by Tone Škoda <tskoda at email.si> Sep 06, 2004
• 453 views

Juergen, i didnt write it yet so your functions look good
but when i try to run it i get this error:

C:\EUPHORIA\include\dll.e:50 in function define_c_func()
type_check failure, lib is {}
... called from C:\EUPHORIA\include\bit.e:188
--> see ex.err

bit.e line 188:
SHIFT_LEFT = define_c_func("", SHL_SPACE, {C_INT, C_INT}, C_INT)

do we have different versions of DLL.E?

10. Re: boolean sequence

• Posted by Tone Škoda <tskoda at email.si> Sep 06, 2004
• 463 views

Juergen Luethje wrote:

 > Using 'define_c_func()' to define not actually a C function, but a
> machine-code routine, requires Eu 2.4 or later. I think you have an
> earlier version, do you?



yes that must be it. i have 2.4 alpha. will update it.

12. Re: boolean sequence

• Posted by "Juergen Luethje" <j.lue at gmx.de> Sep 07, 2004
• 475 views

Tone =A6koda wrote:

> can you also add support for char (8 bit) and short (16 bit). i don't
> know how to handle signed or unsigned numbers for these two types?

You are welcome.

Do you want that those routines use 0 as base index like the bit
routines (AFAIK this is standard for manipulating bits), or that they
use 1 as base index like standard Eu sequences?

This signed/unsigned thing actually makes it a little more complex than
the bit routines. For instance concerning bytes, ATM I'm thinking of two
different possible sets of functions.
One possibility is, to write one separate function for any purpose, this
would result in something like the 7 functions in "set #1".
The other possibility that I'm thinking of is, to write just the
functions that handle unsigned values, and additionally provide two
conversion functions, like in "set #2".

------------------------------------------------------------------------
-- set #1

function put_byte()
   -- It doesn't matter, whether or not the byte to put is signed or unsign=
ed.
function get_byte_u()
   -- return an *unsigned byte*
function get_byte_s()
   -- return a *signed byte*

[The 3 functions above are very similar to poke(), peeku(), and peeks()]

function find_byte_forward_u()
   -- find an *unsigned byte*
function find_byte_forward_s()
   -- find a *signed byte*
function find_byte_reverse_u()
   -- find an *unsigned byte*
function find_byte_reverse_s()
   -- find an *signed byte*

------------------------------------------------------------------------
-- set #2

function put_byte()
   -- It doesn't matter, whether or not the byte to put is signed or unsign=
ed.

function get_byte_u()
   -- return an *unsigned byte*
function find_byte_forward_u()
   -- find an *unsigned byte*
function find_byte_reverse_u()
   -- find an *unsigned byte*

function unsigned_byte()
   -- convert a signed byte to unsigned
function signed_byte()
   -- convert a unsigned byte to signed

------------------------------------------------------------------------

I hope I was able to express myself clearly. Please tell me, what you
want.

Regards,
   Juergen

14. Re: boolean sequence

• Posted by "Juergen Luethje" <j.lue at gmx.de> Sep 08, 2004
• 438 views

Me wrote:

> Tone Skoda wrote:
>
>> can you also add support for char (8 bit) and short (16 bit). i don't
>> know how to handle signed or unsigned numbers for these two types?
>
> You are welcome.
>
> Do you want that those routines use 0 as base index like the bit
> routines (AFAIK this is standard for manipulating bits), or that they
> use 1 as base index like standard Eu sequences?

<snip>

> function put_byte()
>    -- It doesn't matter, whether or not the byte to put is signed or
>       unsigned.
> function get_byte_u()
>    -- return an *unsigned byte*
> function get_byte_s()
>    -- return a *signed byte*
>
> [The 3 functions above are very similar to poke(), peeku(), and peeks()]

peeku() and peeks() do not exist in Eu, of course. I was meaning peek4u()
and peek4s().

> function find_byte_forward_u()
>    -- find an *unsigned byte*
> function find_byte_forward_s()
>    -- find a *signed byte*
> function find_byte_reverse_u()
>    -- find an *unsigned byte*
> function find_byte_reverse_s()
>    -- find an *signed byte*

<snip>

In the meantime I realized, that it's not necessary to make two
different functions for find_byte_forward() and for find_byte_reverse(),
respectively.

So I think the following functions are straightforward:
---------------------------------------------------------------------
   function put_byte   (sequence_of_long s, integer number, byte val)
   function get_byte_u (sequence_of_long s, integer number)
   function get_byte_s (sequence_of_long s, integer number)
   function find_byte_forward (sequence_of_long s, byte val)
   function find_byte_reverse (sequence_of_long s, byte val)
---------------------------------------------------------------------

Do you want it 0-based or 1-based?

I'll post the byte functions first. When they are OK for you, I'll
easily make the respective functions concerning small integers.

Regards,
   Juergen

-- 
A: Because it considerably reduces the readability of the text.
Q: Why?
A: Top posting.
Q: What is annoying in e-mail and news?

16. Re: boolean sequence

• Posted by Tone Škoda <tskoda at email.si> Sep 08, 2004
• 449 views

Juergen Luethje wrote:


> So I think the following functions are straightforward:
> ---------------------------------------------------------------------
>    function put_byte   (sequence_of_long s, integer number, byte val)
>    function get_byte_u (sequence_of_long s, integer number)
>    function get_byte_s (sequence_of_long s, integer number)
>    function find_byte_forward (sequence_of_long s, byte val)
>    function find_byte_reverse (sequence_of_long s, byte val)
> ---------------------------------------------------------------------
> 
> Do you want it 0-based or 1-based?
> 
> I'll post the byte functions first. When they are OK for you, I'll
> easily make the respective functions concerning small integers.

That looks good.
I would more like it 1-based.

18. Re: boolean sequence

• Posted by "Juergen Luethje" <j.lue at gmx.de> Sep 08, 2004
• 443 views

Tone Skoda wrote:

> i like set #1 much more more because it's simpler for the user of the
> lib.

Agreed.

> i'm not sure what  find_byte_... functions do?

find_byte_forward() is somewhat similar to Euphoria's built-in find().
It returns the number of the lowest order byte in the sequence, that is
equal to a given value (or returns -1, if that value is not found).
It returns a different index than find(), though. Example:

sequence s
s = {#00000000, #00000027}
? find(#27, s)                   --> 2nd element of s
? find_byte_forward(s, #27)      --> 5th byte in s

E.g. for use with put_byte(), of course 5 is the correct index, not 2.

Uhhhh... I just realized that I mixed up the order of the arguments. 
   find_byte_forward(#27, s)
would be better, I think.

Also, since the whole thing is 1-based now, 0 could beused instead of -1,
in order to indicate, that find_byte_... didn't find the given value.
What do you think?

> if you are planning to release a lib out of these functions,

Maybe...
I'll only do so, if I find some nice, self-explanatory function names,
and when I have the time to write a sufficient documentation.

> for the simplicity of the lib for the user it would be good if you
> would add these 2 functions (i couldn't think of better function
> names):
>
> 1. bs_new ()
> function to create new sequence which holds data. so for bitset you
> could use this code:
> sequence_of_int_32bit pattern
> pattern = bs_new (100)
> for i = 1 to 100 do
>     pattern = bs_set (pattern, i)
> end for

Yes, I also thought of that.

> 2. bs_newassign ()
> function to create an array with initial values set and proper size
> auto-made:
> sequence_of_int_32bit pattern
> pattern = bs_newassign ({1, 0, 0, 1, 0, 1, 0})

Great idea!

> this lib will be useful because if i have sequence with strings, i will
> be able to use byte-set and have sequence that is 4x smaller than
> regular eu sequence with strings. that's pretty good if your program
> uses a lot of RAM. and speed for setting and getting members in these
> arrays shouldnt be a problem. the biggest "problem" will be that code
> will be a bit uglier and complicated and existing functions cant be
> used on these arrays.
> so main use of this lib is saving RAM.

100% agreed.
Maybe I should add pack/unpack functions? Then the user can "unpack" a
byte array to a normal sequence, use any existing function that (s)he
wants, and then "re-pack" the normal sequence, to get again a byte
array.

[snipped old text]

Regards,
   Juergen

20. Re: boolean sequence

• Posted by "Juergen Luethje" <j.lue at gmx.de> Sep 10, 2004
• 475 views

Tone Skoda wrote:

> Juergen Luethje wrote:
>
>> Also, since the whole thing is 1-based now, 0 could beused instead of -1,
>> in order to indicate, that find_byte_... didn't find the given value.
>> What do you think?
>
> i agree, same as eu's find ().

<snip>

>> Maybe I should add pack/unpack functions? Then the user can "unpack" a
>> byte array to a normal sequence, use any existing function that (s)he
>> wants, and then "re-pack" the normal sequence, to get again a byte
>> array.
>
> yes, pack and unpack functions will be also needed. i also thought of that
> later.

After I wrote the above text, I realized that the function for "packing"
a normal sequence is the same as the newassign_..() function, that you
proposed. 

> your byte code from other post looks good. thanks.

Her comes the code regarding short integers, with find_..() modified the
way we talked about, and with additional functions new_..(), pack_..()
and unpack_..().

include misc.e     -- for pretty_print()
include bit.e      -- Eu 2.4 or later required

------------------------------------------------------------------------
-- utility functions

function ceil (object x)
   -- the opposite of floor()
   -- x may be an atom or a sequence
   return -floor(-x)
end function

------------------------------------------------------------------------
-- types

global type positive_int (object x)
   if integer(x) then
      return x > 0
   end if
   return 0
end type

type sequence_of_long (object x)
   -- sequence consisting of 32-bit integers (signed or unsigned)
   object t

   if atom(x) then return 0 end if
   for i = 1 to length(x) do
      t = x[i]
      if (not atom(t)) or (t != floor(t))
      or (t < -#80000000) or (#FFFFFFFF < t) then
         return 0
      end if
   end for
   return 1
end type

type short (object x)
   -- signed or unsigned 16-bit integer
   if integer(x) then
      if -#8000 <= x then
         return x <= #FFFF
      end if
   end if
   return 0
end type

type sequence_of_short (object x)
   -- sequence consisting of 16-bit integers (signed or unsigned)
   if atom(x) then return 0 end if
   for i = 1 to length(x) do
      if not short(x[i]) then
         return 0
      end if
   end for
   return 1
end type

------------------------------------------------------------------------
-- * The following functions let us treat sequences consisting of an
--   arbitrary number of 32-bit integers as huge "short integer arrays". *
-- Note: The lowest order short integer is always indexed by 1.

global function new_short (positive_int numShortInts)
   -- Create a new empty "short integer array".
   return repeat(0, ceil(numShortInts/2))
end function

global function put_short (sequence_of_long s, positive_int number, short val)
   -- Store 'val' in the short integer in 's', that is indexed by 'number'.
   -- It doesn't matter, whether 'val' is signed or unsigned
   -- (like with the built-in procedure poke4()).
   integer n

   n = ceil(number/2)
   if n > length(s) then
      return -1                   -- error
   end if

   s[n] = or_bits(s[n], c_func( SHIFT_LEFT, {and_bits(val, #FFFF),
                                remainder(number+1,2)*16} ))
   return s
end function

global function pack_short (sequence_of_short s)
   -- Create a new "short integer array", and assign the values in 's' to it.
   -- It doesn't matter, whether the values in 's' are signed or unsigned.
   sequence ret
   integer n

   ret = repeat(0, ceil(length(s)/2))
   for i = 1 to length(s) do
      n = ceil(i/2)
      ret[n] = or_bits(ret[n], c_func( SHIFT_LEFT, {and_bits(s[i], #FFFF),
                                       remainder(i+1,2)*16} ))
   end for
   return ret
end function

global function get_short_u (sequence_of_long s, positive_int number)
   -- Return the short integer in 's', that is indexed by 'number', as an
   -- *unsigned* value.
   integer n

   n = ceil(number/2)
   if n > length(s) then
      return {}                   -- error
   end if

return and_bits(c_func( SHIFT_RIGHT, {s[n], remainder(number+1,2)*16} ),
   #FFFF)
end function

global function get_short_s (sequence_of_long s, positive_int number)
   -- Return the short integer in 's', that is indexed by 'number', as a
   -- *signed* value.
   integer n, val

   n = ceil(number/2)
   if n > length(s) then
      return {}                   -- error
   end if

val = and_bits(c_func( SHIFT_RIGHT, {s[n], remainder(number+1,2)*16} ),
   #FFFF)
   if val > #7FFF then
      val -= #10000               -- convert to signed
   end if
   return val
end function

global function unpack_short_u (sequence_of_long s)
-- "Unpack" the values in a "short integer array" to a normal Euphoria
   sequence,
   -- treating the short integers as *unsigned* values.
   sequence ret
   integer n

   ret = repeat(0, length(s)*2)
   for i = 1 to length(ret) do
      n = ceil(i/2)
ret[i] = and_bits(c_func( SHIFT_RIGHT, {s[n], remainder(i+1,2)*16} ),
      #FFFF)
   end for
   return ret
end function

global function unpack_short_s (sequence_of_long s)
-- "Unpack" the values in a "short integer array" to a normal Euphoria
   sequence,
   -- treating the short integers as *signed* values.
   sequence ret
   integer n, val

   ret = repeat(0, length(s)*2)
   for i = 1 to length(ret) do
      n = ceil(i/2)
      val = and_bits(c_func( SHIFT_RIGHT, {s[n], remainder(i+1,2)*16} ), #FFFF)
      if val > #7FFF then
         val -= #10000            -- convert to signed
      end if
      ret[i] = val
   end for
   return ret
end function

global function find_short_forward (short val, sequence_of_long s)
   -- Return the number of the lowest order short integer in 's', that is equal
   -- to 'val' (or return -1, if 'val' is not found).
   -- It doesn't matter, whether 'val' is signed or unsigned.
   atom t

   if val < 0 then
      val += #10000               -- convert to unsigned
   end if

   for i = 1 to length(s) do
      t = s[i]
      for k = 1 to 2 do
         if and_bits(t, #FFFF) = val then
            return (i-1)*2 + k
         end if
         t = c_func( SHIFT_RIGHT, {t, 16} )
      end for
   end for

   return 0                       -- val not found
end function

global function find_short_reverse (short val, sequence_of_long s)
   -- Return the number of the highest order short integer in 's', that is equal
   -- to 'val' (or return -1, if 'val' is not found).
   -- It doesn't matter, whether 'val' is signed or unsigned.
   atom t

   if val < 0 then
      val += #10000               -- convert to unsigned
   end if

   for i = length(s) to 1 by -1 do
      t = s[i]
      for k = 2 to 1 by -1 do
         t = c_func( ROTATE_LEFT, {t, 16} )
         if and_bits(t, #FFFF) = val then
            return (i-1)*2 + k
         end if
      end for
   end for

   return 0                       -- val not found
end function

------------------------------------------------------------------------

-- * Demo * --
object s
sequence_of_long pattern
sequence p
positive_int numShortInts
integer fn
short val

fn = open("short.txt", "w")
numShortInts = 6

pattern = new_short(numShortInts)
p = "0"
for i = 1 to ceil(numShortInts/2)-1 do
   p &= ",0"
end for

without warning                        -- no short-circuite warning, please

for no = 1 to numShortInts + 1 do
   val = rand(65536+32768)-32769       -- signed or unsigned short integer
   s = put_short(pattern, no, val)     --                  [-#8000, #FFFF]
   printf(fn, "s = put_short({%s}, %d, #%04x)", {p, no, and_bits(val, #FFFF)})
   puts(fn, "\n-> s = ")
   if sequence(s) then
      pretty_print(fn, s, {0,3,1,78,"#%08x","#%08x"})
      if val <  0 and val != get_short_s(s, no) then
         puts(fn, "* Error *\n")
         printf(fn, "  val           = #%04x\n", {val})
         printf(fn, "  get_short_s() = #%04x\n", {get_short_s(s, no)})
      elsif val >= 0 and val != get_short_u(s, no) then
         puts(fn, "* Error *\n")
         printf(fn, "  val           = #%04x\n", {val})
         printf(fn, "  get_short_u() = #%04x\n", {get_short_u(s, no)})
      end if
      printf(fn, "-> find_short_forward(#%04x, s) = %d\n",
                     {and_bits(val, #FFFF), find_short_forward(val, s)})
      printf(fn, "-> find_short_reverse(#%04x, s) = %d\n",
                     {and_bits(val, #FFFF), find_short_reverse(val, s)})
   else
      printf(fn, "%d\n", {s})
   end if
   puts(fn, "\n")
end for

puts(fn, "---------------------------------------\n\n")

s = pack_short({-3,-2,-1,0,1,2,3})
pretty_print(fn, s, {0,3,1,78,"#%08x","#%08x"})
puts(fn, "\n")
pretty_print(fn, unpack_short_s(s), {})
pretty_print(fn, unpack_short_u(s), {})

close(fn)
puts(1, "finished\n")

Regards,
   Juergen