[PATCH v2 0/5] improve sign extension API

[PATCH v2 0/5] improve sign extension API

[Martin Kepplinger]

PATCH 1 improves the doc of sign_extend32()
It should help to avoid different manual approaches to sign extension

PATCH 2 adds sign_extend64()

PTACH 3-5 are (untested) example users of sign_extend64()

changelog
---------
v2: fix a typo and add examples for sign_extend64()

[PATCH 1/5] bitops.h: Improve sign_extend32()'s documentation

[Martin Kepplinger]

It is often overlooked that sign_extend32(), despite it's name, is safe
to use for 16 and 8 bit types aswell. This should help that sign extension
isn't done manually some other way.

Signed-off-by: Martin Kepplinger <martin.kepplinger@theobroma-systems.com>
---
 include/linux/bitops.h | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index e635533..5629923 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -164,6 +164,8 @@ static inline __u8 ror8(__u8 word, unsigned int shift)
  * sign_extend32 - sign extend a 32-bit value using specified bit as sign-bit
  * @value: value to sign extend
  * @index: 0 based bit index (0<=index<32) to sign bit
+ *
+ * This is safe to use for 16- and 8-bit types as well.
  */
 static inline __s32 sign_extend32(__u32 value, int index)
 {
-- 
2.1.4

[PATCH 2/5] bitops.h: add sign_extend64()

[Martin Kepplinger]

Months back, this was discussed, see https://lkml.org/lkml/2015/1/18/289
The result was the 64-bit version being "likely fine", "valuable" and
"correct". The discussion only fell asleep but since there are possible
users, let's add it.

Signed-off-by: Martin Kepplinger <martin.kepplinger@theobroma-systems.com>
---
 include/linux/bitops.h | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 5629923..2b8ed12 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -173,6 +173,17 @@ static inline __s32 sign_extend32(__u32 value, int index)
 	return (__s32)(value << shift) >> shift;
 }
 
+/**
+ * sign_extend64 - sign extend a 64-bit value using specified bit as sign-bit
+ * @value: value to sign extend
+ * @index: 0 based bit index (0<=index<64) to sign bit
+ */
+static inline __s64 sign_extend64(__u64 value, int index)
+{
+	__u8 shift = 63 - index;
+	return (__s64)(value << shift) >> shift;
+}
+
 static inline unsigned fls_long(unsigned long l)
 {
 	if (sizeof(l) == 4)
-- 
2.1.4

[PATCH 3/5] arch: sh: use sign_extend64() for sign extension

[Martin Kepplinger]

Signed-off-by: Martin Kepplinger <martin.kepplinger@theobroma-systems.com>
---
 arch/sh/kernel/traps_64.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/sh/kernel/traps_64.c b/arch/sh/kernel/traps_64.c
index 112ea11..d208c27 100644
--- a/arch/sh/kernel/traps_64.c
+++ b/arch/sh/kernel/traps_64.c
@@ -101,7 +101,7 @@ static int generate_and_check_address(struct pt_regs *regs,
 	if (displacement_not_indexed) {
 		__s64 displacement;
 		displacement = (opcode >> 10) & 0x3ff;
-		displacement = ((displacement << 54) >> 54); /* sign extend */
+		displacement = sign_extend64(displacement, 9);
 		addr = (__u64)((__s64)base_address + (displacement << width_shift));
 	} else {
 		__u64 offset;
-- 
2.1.4

[PATCH 4/5] arch: sh: use sign_extend64() for sign extension

[Martin Kepplinger]

Signed-off-by: Martin Kepplinger <martin.kepplinger@theobroma-systems.com>
---
 arch/sh/kernel/cpu/sh5/unwind.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/sh/kernel/cpu/sh5/unwind.c b/arch/sh/kernel/cpu/sh5/unwind.c
index 10aed41..3a4fed4 100644
--- a/arch/sh/kernel/cpu/sh5/unwind.c
+++ b/arch/sh/kernel/cpu/sh5/unwind.c
@@ -159,7 +159,7 @@ static int lookup_prev_stack_frame(unsigned long fp, unsigned long pc,
 
 			/* Sign extend */
 			regcache[dest] =
-				((((s64)(u64)op >> 10) & 0xffff) << 54) >> 54;
+				sign_extend64((((u64)op >> 10) & 0xffff), 9);
 			break;
 		case (0xd0 >> 2): /* addi */
 		case (0xd4 >> 2): /* addi.l */
-- 
2.1.4

Re: [PATCH 4/5] arch: sh: use sign_extend64() for sign extension

[George Spelvin]

>  			/* Sign extend */
>  			regcache[dest] =
> -				((((s64)(u64)op >> 10) & 0xffff) << 54) >> 54;
> +				sign_extend64((((u64)op >> 10) & 0xffff), 9);
>  			break;

If you're cleaning up the code, cleaning it all the way up would be nice.

The mask wasn't necessary in the original, and the cast to (u64)
is unnecessary with sign_extend64.

So the first cleanup stage is
> +				sign_extend64(op >> 10, 9);

You can improve the 64-bit code by teaching GCC to combine the two
right shifts, but the 32-bit code is a disaster:
> +				sign_extend64(op, 19) >> 10;

And, for the benefit of 32-bit processors, you could just use the 32-bit
version and let the 32->64 bit sign extension happen automatically:
> +				sign_extend32(op, 19) >> 10;

Here are the 5 alternatives, fed through gcc -O3, in 32-bit and 64-bit code,
for x86 and ARM architectures:

	32-bit			64-bit
Original:
	sarl	$10, %eax		sarl	$10, %eax
	sall	$22, %eax		salq	$54, %rax
	cltd		 		sarq	$54, %rax
	sarl	$22, %eax

	mov	r0, r0, asr #10
	mov	r1, r0, asl #22
	mov	r0, r1, asr #22
	mov	r1, r1, asr #31

sign_extend64((((u64)op >> 10) & 0xffff), 9):
	sall	$12, %eax		salq	$44, %rax
	andl	$0xffc00000, %eax	sarq	$54, %rax
	cltd
	sarl	$22, %eax

	mov	r3, r0, asr #31		sbfx	x0, x0, 10, 10
	mov	r0, r0, lsr #10
	orr	r0, r0, r3, asl #22
	mov	r1, r0, asl #22
	mov	r0, r1, asr #22
	mov	r1, r1, asr #31

sign_extend64(op >> 10, 9):
	sarl	$10, %eax		sarl	$10, %eax
	sall	$22, %eax		salq	$54, %rax
	cltd				sarq	$54, %rax
	sarl	$22, %eax

	mov	r0, r0, asr #10		asr	w0, w0, 10
	mov	r1, r0, asl #22		sbfx	x0, x0, 0, 10
	mov	r0, r1, asr #22
	mov	r1, r1, asr #31

sign_extend64(op, 19) >> 10:
	sall	$12, %eax		salq	$44, %rax
	pushl	%ebx			sarq	$54, %rax
	movl	%eax, %ecx
	movl	%eax, %ebx
	sarl	$12, %ebx
	sarl	$31, %ecx
	movl	%ebx, %eax
	movl	%ecx, %edx
	shrdl	$10, %edx, %eax
	popl	%ebx
	sarl	$10, %edx

	mov	r1, r0, asl #12		sbfx	x0, x0, 10, 10
	mov	r0, r1, asr #12
	mov	r0, r0, lsr #10
	mov	r1, r1, asr #31
	orr	r0, r0, r1, asl #22


sign_extend32(op, 19) >> 10:
	sall	$12, %eax		sall	$12, %eax
	sarl	$22, %eax		sarl	$22, %eax
	cltq				cltq

	mov	r0, r0, asl #12		sbfx	x0, x0, 10, 10
	mov	r0, r0, asr #22
	mov	r1, r0, asr #31

	(Or if -march is high enough)
	sbfx	r0, r0, #10, #10
	mov	r1, r0, asr #31

[PATCH 5/5] arch: x86: use sign_extend64() for sign extension

[Martin Kepplinger]

Signed-off-by: Martin Kepplinger <martin.kepplinger@theobroma-systems.com>
---
 arch/x86/kernel/cpu/perf_event_msr.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/arch/x86/kernel/cpu/perf_event_msr.c b/arch/x86/kernel/cpu/perf_event_msr.c
index f32ac13..ec863b9 100644
--- a/arch/x86/kernel/cpu/perf_event_msr.c
+++ b/arch/x86/kernel/cpu/perf_event_msr.c
@@ -163,10 +163,9 @@ again:
 		goto again;
 
 	delta = now - prev;
-	if (unlikely(event->hw.event_base == MSR_SMI_COUNT)) {
-		delta <<= 32;
-		delta >>= 32; /* sign extend */
-	}
+	if (unlikely(event->hw.event_base == MSR_SMI_COUNT))
+		delta = sign_extend64(delta, 31);
+
 	local64_add(now - prev, &event->count);
 }
 
-- 
2.1.4

Re: [PATCH 5/5] arch: x86: use sign_extend64() for sign extension

[George Spelvin]

> --- a/arch/x86/kernel/cpu/perf_event_msr.c
> +++ b/arch/x86/kernel/cpu/perf_event_msr.c
> @@ -163,10 +163,9 @@ again:
>  		goto again;
>  
>  	delta = now - prev;
> -	if (unlikely(event->hw.event_base == MSR_SMI_COUNT)) {
> -		delta <<= 32;
> -		delta >>= 32; /* sign extend */
> -	}
> +	if (unlikely(event->hw.event_base == MSR_SMI_COUNT))
> +		delta = sign_extend64(delta, 31);
> +
>  	local64_add(now - prev, &event->count);
>  }

GCC can figure it out wither way, but wouldn't

	delta = (s32)delta;

be simpler than either?