From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:39511) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZBzhq-0004dI-6E for qemu-devel@nongnu.org; Mon, 06 Jul 2015 02:16:43 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZBzhp-0004oH-BP for qemu-devel@nongnu.org; Mon, 06 Jul 2015 02:16:42 -0400 Received: from mail-pd0-x231.google.com ([2607:f8b0:400e:c02::231]:35719) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZBzhp-0004o9-3k for qemu-devel@nongnu.org; Mon, 06 Jul 2015 02:16:41 -0400 Received: by pdbci14 with SMTP id ci14so99857033pdb.2 for ; Sun, 05 Jul 2015 23:16:40 -0700 (PDT) From: Serge Vakulenko Date: Sun, 5 Jul 2015 23:14:50 -0700 Message-Id: <1436163304-6167-3-git-send-email-serge.vakulenko@gmail.com> In-Reply-To: <1436163304-6167-1-git-send-email-serge.vakulenko@gmail.com> References: <1436163304-6167-1-git-send-email-serge.vakulenko@gmail.com> Subject: [Qemu-devel] [PATCH pic32 v3 02/16] pic32: use LCG algorithm for generated random index of TLBWR instruction List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: Serge Vakulenko , Leon Alrae , Aurelien Jarno The LFSR algorithm, used for generating random TLB indexes for TLBWR instruction, was inclined to produce a degenerate sequence in some cases. For example, for 16-entry TLB size and Wired=1, it gives: 15, 6, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2... When replaced with LCG algorithm from ISO/IEC 9899 standard, the sequence looks much better, with about the same computational effort needed. Signed-off-by: Serge Vakulenko --- hw/mips/cputimer.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/hw/mips/cputimer.c b/hw/mips/cputimer.c index 75917cf..58707ed 100644 --- a/hw/mips/cputimer.c +++ b/hw/mips/cputimer.c @@ -28,13 +28,16 @@ /* XXX: do not use a global */ uint32_t cpu_mips_get_random (CPUMIPSState *env) { - static uint32_t lfsr = 1; + static uint32_t seed = 1; static uint32_t prev_idx = 0; uint32_t idx; /* Don't return same value twice, so get another value */ do { - lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xd0000001u); - idx = lfsr % (env->tlb->nb_tlb - env->CP0_Wired) + env->CP0_Wired; + /* Use a simple algorithm of Linear Congruential Generator + * from ISO/IEC 9899 standard. */ + seed = 1103515245 * seed + 12345; + idx = (seed >> 16) % (env->tlb->nb_tlb - env->CP0_Wired) + + env->CP0_Wired; } while (idx == prev_idx); prev_idx = idx; return idx; -- 2.2.2