From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by sympa.inria.fr (Postfix) with ESMTPS id 7A25C7F2AA for ; Thu, 20 Dec 2012 21:18:54 +0100 (CET) Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of thomas.braibant@gmail.com) identity=pra; client-ip=209.85.215.46; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="thomas.braibant@gmail.com"; x-sender="thomas.braibant@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail4-smtp-sop.national.inria.fr: domain of thomas.braibant@gmail.com designates 209.85.215.46 as permitted sender) identity=mailfrom; client-ip=209.85.215.46; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="thomas.braibant@gmail.com"; x-sender="thomas.braibant@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-la0-f46.google.com) identity=helo; client-ip=209.85.215.46; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="thomas.braibant@gmail.com"; x-sender="postmaster@mail-la0-f46.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqwBABVw01DRVdcujWdsb2JhbABFvWgIFg4BAQEBCQkLCRIGI4IfAQVAARseAwwGEDsiAREBBQEciBkBAw+adIwzgnuFIQoZJw1ZiHYBBQyNZYMpA5YLjmgWKYQW X-IronPort-AV: E=Sophos;i="4.84,326,1355094000"; d="scan'208";a="166460114" Received: from mail-la0-f46.google.com ([209.85.215.46]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 20 Dec 2012 21:18:53 +0100 Received: by mail-la0-f46.google.com with SMTP id p5so3751679lag.19 for ; Thu, 20 Dec 2012 12:18:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=CcNLzhgHOTp1544baGnRo1jkbz0nz/OV7OU9C09aVEo=; b=KFJDtFG6TK3CtiFo6wMWWKI0RK34N2dKgXkvJ7SLCwIgPMhLWQgEY8HMAhokPNJ1aA aL8wnElEOQk5ZdWjulioOlEv+Jcm9zvemKwwtwVykxuJowpIcQ8hMdk2rKJi5j2Cy2pD 0k+RxaixOxqh3JFK5OqKyUi2YwyMMhS3Lxfe7DrI15+CpzCKoKYuQ1KT6f3NR8TyPRRW qxg7Ktjlx8dFnkQWlmjQNSAEJH7odvuMyX8QVLSO/RH9RaRK9H/RSHNySDZGCiu8VA4l RLFIRACTs00UvJtynFNqJ7yYbG4Jd17g8dGgHYlWwc73KesmyRdkC8pJ9h8IZYmz7gk2 veEQ== Received: by 10.152.111.41 with SMTP id if9mr9921415lab.23.1356034732715; Thu, 20 Dec 2012 12:18:52 -0800 (PST) MIME-Version: 1.0 Received: by 10.114.29.197 with HTTP; Thu, 20 Dec 2012 12:18:32 -0800 (PST) In-Reply-To: References: From: Thomas Braibant Date: Thu, 20 Dec 2012 21:18:32 +0100 Message-ID: To: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Subject: [Caml-list] Hashing failure Hi list, I have a piece of code that looks like this. let hkey = H.hash d in (* a custom hash function *) let index = hkey mod (Array.length t.table) in let bucket = t.table.(index) in (* 1 *) the line marked with 1 was generating an index out of bounds exception. It appeared that it was because index was negative, a problem I knew of when using mod ... So I added an abs around index let hkey = H.hash d in let index = abs (hkey mod (Array.length t.table)) in let bucket = t.table.(index) in (* 1 *) But it yields the same exception... This seemed completely unbelievable, till I realized that - x mod y may return a negative value if x is less than 0 - abs x may return a negative value if x is min_int So I tried to reproduce this behavior with the following code: let t = Array.create 17 0;; let hkey = min_int in let index = (abs hkey) mod (Array.length t) in t.(index);; which yields an out of bound. Bingo. It turns out that some value of the length of t will result in an error, and some will not (e.g., 16) ... My question is : is there a safe way to bullet-proof my code against these pathological cases, without too much hinderance (this is some code whose efficiency is critical...) Thomas