C / C ++에서 부호없는 왼쪽 시프트 이전의 마스킹이 너무 편집증 적입니까?

C / C ++에서 부호없는 왼쪽 시프트 이전의 마스킹이 너무 편집증 적입니까?

---

이 질문은 내가 C / C ++로 암호화 알고리즘 (예 : SHA-1)을 구현하고, 이식 가능한 플랫폼에 구애받지 않는 코드를 작성하고, 정의되지 않은 동작을 철저히 피하면서 동기를 부여 받았습니다 .

표준화 된 암호화 알고리즘이이를 구현하도록 요청한다고 가정합니다.

b = (a << 31) & 0xFFFFFFFF

여기서, a및 b32 비트 정수 부호가. 결과에서 우리는 최하위 32 비트 위의 모든 비트를 버립니다.

---

첫 번째 순진한 근사치 int로 대부분의 플랫폼에서 32 비트 너비 라고 가정 할 수 있으므로 다음과 같이 작성합니다.

unsigned int a = (...);
unsigned int b = a << 31;

이 코드는 int일부 시스템에서는 16 비트, 다른 시스템에서는 64 비트, 심지어는 36 비트 이므로 모든 곳에서 작동하지 않습니다 . 그러나를 사용 stdint.h하면 다음 uint32_t유형 으로이 코드를 개선 할 수 있습니다 .

uint32_t a = (...);
uint32_t b = a << 31;

그래서 우리는 끝났 죠? 그게 제가 몇 년 동안 생각했던 것입니다. ... 정답이 아닙니다. 특정 플랫폼에 다음이 있다고 가정합니다.

// stdint.h
typedef unsigned short uint32_t;

C / C ++에서 산술 연산을 수행하는 규칙은 유형 (예 short:)이보다 좁 으면 모든 값이 맞을 수 있거나 그렇지 않은 경우 int확장된다는 것 입니다.intunsigned int

컴파일러 short가 32 비트 (서명 됨)와 int48 비트 (서명 됨)로 정의한다고 가정 해 보겠습니다 . 다음 코드 줄 :

uint32_t a = (...);
uint32_t b = a << 31;

효과적인 의미 :

unsigned short a = (...);
unsigned short b = (unsigned short)((int)a << 31);

참고 a로 승격 int의 때문에 모든 ushort(예 uint32에) 적합 int(예 int48).

그러나 이제 문제가 있습니다. 0이 아닌 비트를 부호있는 정수 유형의 부호 비트로 이동하는 것은 정의되지 않은 동작 입니다. 이 문제 uint32는 우리 가 (왼쪽 시프트가 괜찮을 것 같은) int48승진되는 대신- 로 승격 되었기 때문에 발생했습니다 uint48.

---

내 질문은 다음과 같습니다.

1. 내 추론이 정확하고 이것이 이론상 정당한 문제입니까?

2. 모든 플랫폼에서 다음 정수 유형이 너비의 두 배이기 때문에이 문제를 무시해도 안전합니까?

3. 다음과 같이 입력을 사전 마스킹하여이 병리 적 상황을 올바르게 방어하는 것이 좋은 생각입니까? : b = (a & 1) << 31;. (이것은 모든 플랫폼에서 반드시 정확할 것입니다. 그러나 이것은 속도가 중요한 암호화 알고리즘을 필요 이상으로 느리게 만들 수 있습니다.)

설명 / 편집 :

• C 또는 C ++ 또는 둘 다에 대한 답변을 수락합니다. 적어도 하나의 언어에 대한 답을 알고 싶습니다.

• 사전 마스킹 로직은 비트 회전을 손상시킬 수 있습니다. 예를 들어 GCC는 b = (a << 31) | (a >> 1);어셈블리 언어의 32 비트 비트 회전 명령어로 컴파일 됩니다. 그러나 왼쪽 시프트를 사전 마스킹하면 새 논리가 비트 회전으로 변환되지 않을 수 있습니다. 즉, 이제 1 대신 4 개의 작업이 수행됩니다.

---

문제의 C 측에 말하면

1. 내 추론이 정확하고 이것이 이론상 정당한 문제입니까?

이전에 고려하지 않았던 문제지만 분석에 동의합니다. C는 승격 된 왼쪽 피연산자 <<의 유형과 관련 하여 연산자 의 동작을 정의하며 , 해당 피연산자의 원래 유형이 인 경우 정수 승격으로 인해 (서명 된) 것으로 간주 할 수 있습니다. 나는 현대 기계에서 실제로 그것을 볼 것이라고 기대하지 않지만, 개인적 기대와는 달리 실제 표준에 맞게 프로그래밍하는 것입니다.intuint32_t

2. 모든 플랫폼에서 다음 정수 유형이 너비의 두 배이기 때문에이 문제를 무시해도 안전합니까?

C는 실제로 유비쿼터스이지만 정수 유형간에 이러한 관계를 요구하지 않습니다. 그러나 표준에만 의존하기로 결정했다면, 즉 엄격하게 준수하는 코드를 작성하는 데 어려움을 겪고 있다면 그러한 관계에 의존 할 수 없습니다.

3. 다음과 같이 입력을 미리 마스킹하여이 병리 적 상황을 올바르게 방어하는 것이 좋은 생각입니까? : b = (a & 1) << 31 ;. (이것은 모든 플랫폼에서 반드시 정확할 것입니다. 그러나 이것은 속도가 중요한 암호화 알고리즘을 필요 이상으로 느리게 만들 수 있습니다.)

이 유형 unsigned long은 32 개 이상의 값 비트를 갖도록 보장되며 정수 승격에 따라 다른 유형으로 승격되지 않습니다. 많은 공통 플랫폼에서과 정확히 동일한 표현을 가지며 uint32_t동일한 유형일 수도 있습니다. 따라서 나는 다음과 같은 표현을 쓰는 경향이 있습니다.

uint32_t a = (...);
uint32_t b = (unsigned long) a << 31;

또는을 a계산할 때 중간 값으로 만 필요한 경우 시작 b하려면 unsigned long로 선언하십시오 .

---

Q1 : 전환 전 마스킹 은 OP가 우려하는 정의되지 않은 동작을 방지합니다.

Q2 : "... 모든 플랫폼에서 다음 정수 유형은 너비의 두 배이기 때문에?" -> 아니요. "다음"정수 유형은 2x보다 작거나 동일한 크기 일 수 있습니다.

다음은 .NET Framework가있는 모든 호환 C 컴파일러에 대해 잘 정의되어 있습니다 uint32_t.

uint32_t a; 
uint32_t b = (a & 1) << 31;

Q3 : uint32_t a; uint32_t b = (a & 1) << 31;마스크를 수행하는 코드가 발생하지 않을 것으로 예상됩니다. 실행 파일에는 필요하지 않습니다. 소스에서만 가능합니다. 마스크가 발생하면 더 나은 컴파일러를 사용하면 속도가 문제가됩니다.

제안 된 바와 같이 , 이러한 변화로 부호 없음을 강조하는 것이 좋습니다.

uint32_t b = (a & 1U) << 31;

---

@ John Bollinger 좋은 대답은 OP의 특정 문제를 처리하는 방법을 자세히 설명합니다.

The general problem is how to form a number that is of at least n bits, a certain sign-ness and not subject to surprising integer promotions - the core of OP's dilemma. The below fulfills this by invoking an unsigned operation that does not change the value - effective a no-op other than type concerns. The product will be at least the width of unsigned or uint32_t. Casting, in general, may narrow the type. Casting needs to be avoided unless narrowing is certain to not occur. An optimization compiler will not create unnecessary code.

uint32_t a;
uint32_t b = (a + 0u) << 31;
uint32_t b = (a*1u) << 31;

---

Taking a clue from this question about possible UB in uint32 * uint32 arithmetic, the following simple approach should work in C and C++:

uint32_t a = (...);
uint32_t b = (uint32_t)((a + 0u) << 31);

The integer constant 0u has type unsigned int. This promotes the addition a + 0u to uint32_t or unsigned int, whichever is wider. Because the type has rank int or higher, no more promotion occurs, and the shift can be applied with the left operand being uint32_t or unsigned int.

The final cast back to uint32_t will just suppress potential warnings about a narrowing conversion (say if int is 64 bits).

A decent C compiler should be able to see that adding zero is a no-op, which is less onerous than seeing that a pre-mask has no effect after an unsigned shift.

---

To avoid unwanted promotion, you may use the greater type with some typedef, as

using my_uint_at_least32 = std::conditional_t<(sizeof(std::uint32_t) < sizeof(unsigned)),
                                              unsigned,
                                              std::uint32_t>;

---

For this segment of code:

uint32_t a = (...);
uint32_t b = a << 31;

To promote a to a unsigned type instead of signed type, use:

uint32_t b = a << 31u;

When both sides of << operator is an unsigned type, then this line in 6.3.1.8 (C standard draft n1570) applies:

Otherwise, if both operands have signed integer types or both have unsigned integer types, the operand with the type of lesser integer conversion rank is converted to the type of the operand with greater rank.

---

The problem you are describing is caused you use 31 which is signed int type so another line in 6.3.1.8

Otherwise, if the type of the operand with signed integer type can represent all of the values of the type of the operand with unsigned integer type, then the operand with unsigned integer type is converted to the type of the operand with signed integer type.

forces a to promoted to a signed type

---

Update:

This answer is not correct because 6.3.1.1(2) (emphasis mine):

...

If an int can represent all values of the original type (as restricted by the width, for a bit-field), the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions.58) All other types are unchanged by the integer promotions.

and footnote 58 (emphasis mine):

58) The integer promotions are applied only: as part of the usual arithmetic conversions, to certain argument expressions, to the operands of the unary +, -, and ~ operators, and to both operands of the shift operators, as specified by their respective subclauses.

Since only integer promotion is happening and not common arithmetic conversion, using 31u does not guarantee a to be converted to unsigned int as stated above.

참고URL : https://stackoverflow.com/questions/39964651/is-masking-before-unsigned-left-shift-in-c-c-too-paranoid