Best way to deal with fixed size ints (32 bit, 64 bits, etc.)

[Iván Zaera Avellón]

Hi all:

I had a hard time yesterday porting hash algorithm RIPEMD160 from Java to Dart. The reason was the arithmetic for fixed size ints and now I understand that I have not clear how this entities are supposed to be handled in Dart.

My doubts are: we have typed_data for efficient arrays of Uint8, Uint32 and the like, but all those lists implement List<int>. Thus, when I want to manipulate any of the values inside those lists I have to resort to int arithmetic which is, to say the least, difficult for fixed size (as Dart ints are of arbitrary precission, which implies variable binary size).

We also have fixnum package of Int32 and Int64, which I ended up using to port Java's code quickly.

But now I have two unrelated packages which don't talk to each other (typed_data and fixnum) and I must convert from int to Int32 and back and code gets messy.

What would be the correct way to do it? 

Should I implement my own classes|functions for this purposes and use List<my class for this purposes>? 

Should I use Uint8List and fixnum and convert between them as I'm doing now?

Is there any other efficient package for fixed size arithmetic and logical operations I'm missing?

Thanks in advance,

Ivan

[Iván Zaera Avellón]

OK, nobody answers. I think I'll simplify my question ;-) .

How are we supposed to handle bit-level data when both arithmetical and bitwise logical transformations are needed? (Of course I mean in the most efficient way).

Thanks in advance.

[Alex Tatumizer]

Ivan,

the issue was discussed ad nauseam over the last year in this mailing list. Use keywords like "crypto", "uint32", "unboxed" etc to find more detailed info.

The bottom line is: there's no way to *efficiently* implement crypto algos right now, and it's not a focus of upcoming 1.0 release.

Fixnum module you mentioned is a kind of etude towards future implementation, not a real thing.

To compensate for disappointment, listen to something good:

http://www.youtube.com/watch?v=ziMm6kvdwuA

[Iván Zaera Avellón]

OK. Thanks Alex. That's enough. At least now I know that there's nothing better ;-) .

I will keep, anyway, implementing crypto. Just being aware that performance will be bad. But at least we will have some crypto available, which IMHO, it's a very important functionality for some real life applications.

--
For other discussions, see https://groups.google.com/a/dartlang.org/
 
For HOWTO questions, visit http://stackoverflow.com/tags/dart
 
To file a bug report or feature request, go to http://www.dartbug.com/new

To unsubscribe from this group and stop receiving emails from it, send an email to misc+uns...@dartlang.org.

[Justin Fagnani]

+Chris who might have ideas on integration between fixnum and typed-arrays.

[Alex Tatumizer]

How about the following idea: *instead* of classes like Int32 or Int64 etc, introduce one single class Processor with, say, 4 32-bit registers x,y,z,w, 2 64-bit registers (pairs of 32-bit registers xy, zw), single 128-bit register xyzw, carry flag and appropriate instructions. The trick is that we won't need explicit types like int32 at all  - they look like regular ints when passed outside of conext of processor.

We do similar thing with SIMD registers, it's the same concept.

[Iván Zaera Avellón]

That would also make it easier to expose crypto specific instructions (like the ones for AES). Wouldn't it?

2013/10/18 Alex Tatumizer <tatu...@gmail.com>

[Chris Bracken]

A few thoughts from my end. Keep in mind that aside from fixed-width arithmetic, one of the key uses we've been dealing with in fixnum is getting around the lack of 64-bit ints when running dart2js'ed. That may be as basic as wanting 64-bit DB identifiers in the UI. For those cases fixnum is a very simple solution, so I don't see it going away.

As you've noted, if you're using fixnum with typed_data today, you need to mediate between the two; e.g. fromBytes() or fromInts(). API-wise, we don't currently have any plans to add dependencies between these two packages at the moment so what you've got may be as good as it gets today.

We've made some very significant performance improvements to fixnum over the last few months, but as Alex mentioned, the crypto usecase is not a focus for 1.0. That said, bugs/enhancement requests on dartbug.com are always appreciated!

Cheers,

Chris

[dangli...@gmail.com]

All that need in this case is:
1. Stop using in JS runtime native numbers directly.
2. Introducing new "value type" class and begin using it.

For first item I can say that currently dart2js compiler utilize native javascript numeric type. This is good. This is fast execution time in JS  
environment.
But this is not right way for introducing in Dart new native numeric types.

For the second item I can say that Dart currently has "value type" but not utilized it at full power. This type in Dart called "num".

What is solution in this case?

Stop using in JS runtime native numbers means not using at all assignment of "raw" numeric constants.
I.e.
#dart
var integer = 512; // int (by default "bigint"), extends num
var byte = 512 as Byte; // uint8, extends num
var int64 = byte.toInt64(); // int64, extends num
var int32 = new Int32(512); // int32, extends num

#JS
integer = new P.int(512);
byte = new P.Byte(512);
int64 = byte.toInt64();
int32 = new P.Int32(512);

I.e.
Operate in JS runtime not with native numbers but with the "boxed" numbers.
Always. This approach may allow use implementations of any kind of numbers in JS.
Not only native (big integers) but also other types from bytes to 64-bit numbers. Signed and unsigned.

With this approach time will be lost only on assignment operations ("boxing").
In all other case this would be no so big sense because Dart already not used direct arithmetic operations in JS.

I.e.
#dart
a.i1 = x + 5;

#JS
a.i1 = J.$add$ns(i, 5);

Must be
#JS
a.i1 = J.$add$ns(a.i1, i, 5);

#Currently
J.$add$ns = function(receiver, a0) {
  if (typeof receiver == "number" && typeof a0 == "number")
    return receiver + a0;
  return J.getInterceptor$ns(receiver).$add(receiver, a0);
};

#Must be
J.$add$ns = function(destination, receiver, a0) {
  if(typeof destination == "undefined" || typeof destination == "number") {
    if (typeof receiver == "number" && typeof a0 == "number")
      return receiver + a0;
  }
  return destination.$add(receiver, a0);
};

I think you understand what I meant to say.
If this emulation of value types would be implemented in JS then it can be implemented (simply) in VM.

P.S.

[Alex Tatumizer]

Just in case, I opened an issue for Processor class:

https://code.google.com/p/dart/issues/detail?id=14249

If you like the idea, please star. 

[dangli...@gmail.com]

>> Just in case, I opened an issue for Processor class:

I not agree with you. This is too complex and not the best way because without compiler support.

Without support of conversion operator overloading in language this would be not possible implement good support of numeric types in right way.
At least explicit conversion operator overloading must be added in language specification.

Example

void main() {
  var integer = new MyUInt(5);
  var byte = new MyByte(5);
  integer = byte as MyUInt; // type 'MyByte' is not a subtype of type 'MyUInt' in type cast.
}

class MyByte {
  final int value;

  MyByte(this.value) {
    if(value == null || value < 0 || value > 0xff) {
      throw new ArgumentError("value: $value");
    }
  }

  operator explicit(other) {
    if(other is MyByte) {
      return other;
    } else if(other is int) {
      return new MyByte(Utils.convertToUInt8(other));
    }
  }
}

class MyUInt {
  final int value;

  MyUInt(this.value) {
    if(value == null || value < 0 || value > 0xffffffff) {
      throw new ArgumentError("value: $value");
    }
  }

  operator explicit(other) {
    if(other is MyUInt) {
      return other;
    } else if(other is int) {
      return new MyUInt(Utils.convertToUInt32(other));
    } else if(other is MyByte) {
      return new MyUInt(other.value);
    }
  }
}

class Utils {
  static int convertToUInt32(int value) {
    //
  }

  static int convertToUInt8(int value) {
    //
  }
}

Also allowing to overloading implicit operator conversion would be very useful.
But (for better result in analyzer) this required supporting this kind of declaration.

class MyUInt {
  operator implicit(int|MyUInt|MyByte other) {
    if(other is MyUInt) {
      return other;
    } else if(other is int) {
      return new MyUInt(other);
    } else if(other is MyByte) {
      return new MyUInt(other.value);
    }
  }
}

This would be allow use this implicit conversions.

integer = byte;

But this is not so simply in Dart. And at first time explicit conversion operator overloading must be enough.

суббота, 19 октября 2013 г., 15:20:57 UTC+6 пользователь Alex Tatumizer написал:

[dangli...@gmail.com]

Sorry. Errata:

1.

Also possible with overloaded explicit conversion operator:

var integer = 5 as MyUInt;

var byte = 5 as MyByte;

This is not harder than this operation "byte = byte + 5". Just overloaded operator.
Only other direction.
var byte = 5 as MyByte; // MyByte.explicit(5);

2.

operator explicit(other) {

    if(other is! AllowedType) {

      throw new YourTypeConverionError();

    }

}

[Alex Tatumizer]

The whole point of Processor is that you need less explicit types, operation names etc - it's like having a number of pre-declared vars with appropriate types, and the meaning of operation is derived from context. E.g.

p.a32=p.b8 - will copy 8 bits from b register to a and clear next 24 bits of a.

Similarly, p.a64=p.b32*p.c32 - will multiply 32-bit operands and place 64-bit product into a.

It's easy to compile these operations into machine instructions. More importantly, it makes low-level programming natural - as opposed to the alternative where you need to call constructors and generally write a lot of verbose boilerplate.

[dangli...@gmail.com]

New issue: Allow possibility to override explicit conversion operator
Issue: 14251

[Justin Fagnani]

But there is no conversion operator to override. Dart's "as" isn't a cast, it's a type check.

On Oct 19, 2013 9:51 AM, <dangli...@gmail.com> wrote:

New issue: Allow possibility to override explicit conversion operator
Issue: 14251

[Stephen Adams]

On Thu, Oct 17, 2013 at 12:15 AM, Iván Zaera Avellón <iza...@gmail.com> wrote:

OK, nobody answers. I think I'll simplify my question ;-) .

How are we supposed to handle bit-level data when both arithmetical and bitwise logical transformations are needed? (Of course I mean in the most efficient way).

int has two methods for narrowing a value to a given number of bits:

http://api.dartlang.org/docs/releases/latest/dart_core/int.html#toSigned

http://api.dartlang.org/docs/releases/latest/dart_core/int.html#toUnsigned

These are useful when you want to keep a computed value in a range.

dart2js has the limitation that bitwise operations on int values is restricted as though the implementations all used 

"return result.toUnsigned(32)"

Thanks in advance.

El 14/10/2013 13:00, "Iván Zaera Avellón" <iza...@gmail.com> escribió:

Hi all:

I had a hard time yesterday porting hash algorithm RIPEMD160 from Java to Dart. The reason was the arithmetic for fixed size ints and now I understand that I have not clear how this entities are supposed to be handled in Dart.

My doubts are: we have typed_data for efficient arrays of Uint8, Uint32 and the like, but all those lists implement List<int>. Thus, when I want to manipulate any of the values inside those lists I have to resort to int arithmetic which is, to say the least, difficult for fixed size (as Dart ints are of arbitrary precission, which implies variable binary size).

We also have fixnum package of Int32 and Int64, which I ended up using to port Java's code quickly.

But now I have two unrelated packages which don't talk to each other (typed_data and fixnum) and I must convert from int to Int32 and back and code gets messy.

What would be the correct way to do it? 

Should I implement my own classes|functions for this purposes and use List<my class for this purposes>? 

Should I use Uint8List and fixnum and convert between them as I'm doing now?

Is there any other efficient package for fixed size arithmetic and logical operations I'm missing?

Thanks in advance,

Ivan

[dangli...@gmail.com]

>> But there is no conversion operator to override. Dart's "as" isn't a cast, it's a type check.

Please read this topic Allow possibility to override explicit conversion operator. At least first 4-5 messages.
Using for this purpose operator "as" is my mistake.
I am talking only about adding user definable (overriden operator) of type cast (conversion between incompatible types).
Used not often but very magic and useful.

[Alex Tatumizer]

> int has two methods for narrowing a value to a given number of bits

1. Since when?

2. Are they expected to be as good as AND (performance-wise)?

3. Is it possible to find out the bitness of processor? Platform class doesn't seem to provide this info.

[Iván Zaera Avellón]

Mmm, that sounds very good. Are they supposed to be faster than Int32?

I'll reply myself:

** Int32.fromInt is implemented as:  _i = (i & 0x7fffffff) - (i & 0x80000000);

** JSInt.toUnsigned is implemented as: return this & ((1 << width) - 1);

So they seem similar (3 operations each). This makes me think that maybe an Uint32 class could be faster than both the previous, as:

** Uint32.fromInt could be implemented as: _i = (i & 0xffffffff);

Which is just 1 op.

Why don't we have Uint32, Uintx and Uint64? Wouldn't they be faster than Int32, Intx, Int64 because we don't have to deal with the sign?

2013/10/19 Stephen Adams <s...@google.com>