Esoteric bit operations.

runtime/lib/integers.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/bootstrap_natives.h"
 
 #include "vm/bigint_operations.h"
 #include "vm/dart_entry.h"
 #include "vm/exceptions.h"
 #include "vm/native_entry.h"
@@ skipping 17 matching lines @@
         !BigintOperations::FitsIntoInt64(bigint);
   }
   if (i.IsMint()) {
     const Mint& mint = Mint::Cast(i);
     return !Smi::IsValid64(mint.value());
   }
   return true;
 }
 
 
+static int bitLength(uint64_t value) {

[srdjan, 2013/09/06 15:35:34]

s/bitLength/BitLength/  (Dart vs C++ style)

[sra1, 2013/09/06 22:11:57]

Done.

+  // TODO(sra):  Use (64 - __builtin_clzll(value));
+  int result = 0;
+  uint32_t value32;
+  if (value >= (static_cast<uint64_t>(1) << 32)) {

[srdjan, 2013/09/06 15:35:34]

You can use Utils::IsUint(32, value), also for the rest of the code you may use
some of the helper methods in runtime/platforms/utils.h

[sra1, 2013/09/06 22:11:57]

Done.

+    result += 32;
+    value32 = static_cast<uint32_t>(value >> 32);
+  } else {
+    value32 = static_cast<uint32_t>(value);
+  }
+  if (value32 >= (1 << 16)) {
+    result += 16;
+    value32 >>= 16;
+  }
+  if (value32 >= (1 << 8)) {
+    result += 8;
+    value32 >>= 8;
+  }
+  if (value32 >= (1 << 4)) {
+    result += 4;
+    value32 >>= 4;
+  }
+  if (value32 >= (1 << 2)) {
+    result += 2;
+    value32 >>= 2;
+  }
+  if (value32 >= (1 << 1)) {
+    result += 1;
+    value32 >>= 1;
+  }
+  if (value32 >= 1) {
+    result += 1;
+  }
+  return result;
+}
+
+
 DEFINE_NATIVE_ENTRY(Integer_bitAndFromInteger, 2) {
   const Integer& right = Integer::CheckedHandle(arguments->NativeArgAt(0));
   GET_NON_NULL_NATIVE_ARGUMENT(Integer, left, arguments->NativeArgAt(1));
   ASSERT(CheckInteger(right));
   ASSERT(CheckInteger(left));
   if (FLAG_trace_intrinsified_natives) {
     OS::Print("Integer_bitAndFromInteger %s & %s\n",
         right.ToCString(), left.ToCString());
   }
   const Integer& result =
@@ skipping 272 matching lines @@
   const Smi& operand = Smi::CheckedHandle(arguments->NativeArgAt(0));
   if (FLAG_trace_intrinsified_natives) {
     OS::Print("Smi_bitNegate: %s\n", operand.ToCString());
   }
   intptr_t result = ~operand.Value();
   ASSERT(Smi::IsValid(result));
   return Smi::New(result);
 }
 
 
+DEFINE_NATIVE_ENTRY(Smi_bitLength, 1) {
+  const Smi& operand = Smi::CheckedHandle(arguments->NativeArgAt(0));
+  if (FLAG_trace_intrinsified_natives) {
+    OS::Print("Smi_bitLength: %s\n", operand.ToCString());
+  }
+  int64_t value = operand.AsInt64Value();
+  value ^= value >> (8 * sizeof(value) - 1);  // flip bits if negative.
+
+  intptr_t result = bitLength(value);
+
+  ASSERT(Smi::IsValid(result));
+  return Smi::New(result);
+}
+
+
 // Mint natives.
 
 DEFINE_NATIVE_ENTRY(Mint_bitNegate, 1) {
   const Mint& operand = Mint::CheckedHandle(arguments->NativeArgAt(0));
   ASSERT(CheckInteger(operand));
   if (FLAG_trace_intrinsified_natives) {
     OS::Print("Mint_bitNegate: %s\n", operand.ToCString());
   }
   int64_t result = ~operand.value();
   return Integer::New(result);
 }
 
 
+DEFINE_NATIVE_ENTRY(Mint_bitLength, 1) {
+  const Mint& operand = Mint::CheckedHandle(arguments->NativeArgAt(0));
+  ASSERT(CheckInteger(operand));
+  if (FLAG_trace_intrinsified_natives) {
+    OS::Print("Mint_bitLength: %s\n", operand.ToCString());
+  }
+  int64_t value = operand.AsInt64Value();
+  value ^= value >> (8 * sizeof(value) - 1);  // flip bits if negative.
+
+  intptr_t result = bitLength(value);
+
+  ASSERT(Smi::IsValid(result));
+  return Smi::New(result);
+}
+
+
 DEFINE_NATIVE_ENTRY(Mint_shlFromInt, 2) {
   // Use the preallocated out of memory exception to avoid calling
   // into dart code or allocating any code.
   const Instance& exception =
       Instance::Handle(isolate->object_store()->out_of_memory());
   Exceptions::Throw(exception);
   UNREACHABLE();
   return 0;
 }
 
 
 // Bigint natives.
 
 DEFINE_NATIVE_ENTRY(Bigint_bitNegate, 1) {
   const Bigint& value = Bigint::CheckedHandle(arguments->NativeArgAt(0));
   const Bigint& result = Bigint::Handle(BigintOperations::BitNot(value));
   ASSERT(CheckInteger(value));
   ASSERT(CheckInteger(result));
   return result.AsValidInteger();
 }
 
 
+DEFINE_NATIVE_ENTRY(Bigint_bitLength, 1) {
+  const Bigint& value = Bigint::CheckedHandle(arguments->NativeArgAt(0));
+  return Integer::New(BigintOperations::BitLength(value));
+}
+
+
 DEFINE_NATIVE_ENTRY(Bigint_shlFromInt, 2) {
   // Use the preallocated out of memory exception to avoid calling
   // into dart code or allocating any code.
   const Instance& exception =
       Instance::Handle(isolate->object_store()->out_of_memory());
   Exceptions::Throw(exception);
   UNREACHABLE();
   return 0;
 }
 
 }  // namespace dart