From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53784) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZC20Q-00037i-4F for qemu-devel@nongnu.org; Mon, 06 Jul 2015 04:44:03 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZC20P-0001DW-9D for qemu-devel@nongnu.org; Mon, 06 Jul 2015 04:44:02 -0400 Received: from hall.aurel32.net ([2001:bc8:30d7:100::1]:47142) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZC20P-0001DH-34 for qemu-devel@nongnu.org; Mon, 06 Jul 2015 04:44:01 -0400 Date: Mon, 6 Jul 2015 10:43:59 +0200 From: Aurelien Jarno Message-ID: <20150706084359.GW931@aurel32.net> References: <1436163304-6167-1-git-send-email-serge.vakulenko@gmail.com> <1436163304-6167-3-git-send-email-serge.vakulenko@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1436163304-6167-3-git-send-email-serge.vakulenko@gmail.com> Subject: Re: [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: Serge Vakulenko Cc: Leon Alrae , qemu-devel@nongnu.org On 2015-07-05 23:14, Serge Vakulenko wrote: > 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; This is indeed better, it seems the generated values are also better in the standard Linux case (16 entries, wired = 0). Reviewed-by: Aurelien Jarno -- Aurelien Jarno GPG: 4096R/1DDD8C9B aurelien@aurel32.net http://www.aurel32.net