What is "bit padding" or "padding bits" exactly?

Question

I do not want to molest you with this, but i just can not find anywhere in the internet a well-described explanation for what "bit padding" really is, as well as not in any answer for bit padding-related threads here on StackOverflow.

I also searched ISO 9899-1990 for it, in which "bit padding" is refered to but quite not explained as i need it.

The only content in the web i found about this was here, where only one ridiculously short explanation of one sentence was given, saying:

bit padding:

Bit padding is the addition of one or more extra bits to a transmission or storage unit to make it conform to a standard size.

Some sources identify bit padding as a type of bit stuffing.

Which it at least some sort of information but not enough explanation for me. I don´t quite understand what that means exactly. It also refers to the term "bit stuffing".

When i look at the relative tag here on StockOverflow for "padding", padding is described as:

Extra space inserted into memory structures to achieve address alignment -or- extra space between the frame and the content of an HTML element -or- extra spaces or zeros when printing out values using formatting print commands like, in C, the printf*-family of functions.

Background:

I often find the term "bit padding" in relation of data types, but don´t understand what it is nor what it does exaclty with those.

Thank you very much for any topic-based answer.

it is "Extra space inserted into memory structures to achieve address alignment " Can you ask more specifically? I wouldn't know what to add to what you already posted — 463035818_is_not_an_ai, Oct 17 '19 at 14:50
`I often find the term "bit padding" in relation of data types` - do you have examples? — 500 - Internal Server Error, Oct 17 '19 at 14:51
@formerlyknownas_463035818 Why inserting extra space into memory structures? For which address alignment? — RobertS supports Monica Cellio, Oct 17 '19 at 14:51
@500-InternalServerError [here](http://www.cplusplus.com/reference/cstdint/) for example — RobertS supports Monica Cellio, Oct 17 '19 at 14:52
that link has zero hits for the search "bit padding". Anyhow, that site is known to be riddled with misinformation — 463035818_is_not_an_ai, Oct 17 '19 at 14:53
@500-InternalServerError under the descriptions of the types. — RobertS supports Monica Cellio, Oct 17 '19 at 14:56
well ok I found where they mention padding of bits, nevertheless you better choose a different source. (i am really hesitant to tell others where to read what, but this is one exception) — 463035818_is_not_an_ai, Oct 17 '19 at 14:56
Good read on the subject: https://en.wikipedia.org/wiki/Data_structure_alignment — NathanOliver, Oct 17 '19 at 14:58
Why the downvotes? OP clearly showed research effort, and it looks like a useful and clear question to me, which is asked for an upvote. Downvotes are for questions that show no research effort and are therefore unclear and not useful. Am I missing something? — 89f3a1c, Oct 17 '19 at 15:00
Related question : [Why isn't sizeof for a struct equal to the sum of sizeof of each member?](https://stackoverflow.com/questions/119123/why-isnt-sizeof-for-a-struct-equal-to-the-sum-of-sizeof-of-each-member) — François Andrieux, Oct 17 '19 at 15:06
https://stackoverflow.com/questions/4306186/structure-padding-and-packing — gstukelj, Oct 17 '19 at 15:43

NathanOliver · Answer 1 · 2021-04-14T17:50:59.043

I often find the term "bit padding" in relation of data types, but don´t understand what it is nor what it does exactly with those.

The gist of it is they are "wasted" space. I say "wasted" because while having padding bits makes the object bigger, it can make working with the object much easier (which means faster) and the small space waste can generate huge performance gains. In some cases it is essential because the CPU can't handle working with objects of that size.

Lets say you have a struct like (all numbers are just an example, different platforms can have different values):

struct foo
{
    short a; // 16 bits
    char  b; // 8 bits 
};

and the machine you are working with reads 32 bits of data in a single read operation. Reading a single foo is not a problem since the entire object fits into that 32 bit chunk. What does become a problem is when you have an array. The important thing to remember about arrays is that they are contiguous, there is no space between elements. It's just one object immediately followed by another. So, if you have an array like

foo array[10]{};

With this the first foo object is in a 32 bit bucket. The next element of the array though will be in the first 32 bit bucket and the second 32 bit bucket. This means that the member a is in two separate buckets. Some processors can do this (at a cost) and other processors will just crash if you try to do this. To solve both those problems the compiler will add padding bits to the end of foo to pad out it's size. This means foo actually becomes

struct foo
{
    short a; // 16 bits
    char  b; // 8 bits 
    char  _; // 8 bits of padding
};

And now it is easy for the processor to handle foo objects by themselves or in an array. It doesn't need to do any extra work and you've only added 8 bits per object. You'd need a lot of objects for that to start to matter on a modern machine.

There is also times where you need padding between members of the type because of unaligned access. Lets say you have

struct bar
{
    char c; // 8 bits
    int  d; // 32 bits
};

Now bar is 40 bits wide and d more often then not will be stored in two different buckets again. To fix this the compiler adds padding bits between c an d like

struct bar
{
    char    c; // 8 bits
    char _[3]; // 24 bits
    int     d; // 32 bits
};

and now d is guaranteed to go into a single 32 bit bucket.

'@Nathan Oliver' Thank you very much for this example. I did not know that a machine is reading data per chunks. Thus, it is logically to add bits to that structure to make its elements better readable for the machine, means also of course speed benefits at execution, Ok.. How bit padding is done, when i have only one variable which do not fit at that chunkof 32bit, f.e. `short int a = 145;` ? — RobertS supports Monica Cellio, Oct 17 '19 at 16:11
If that member is part of a class, passing may be added. If the object is just a local variable the compiler may decide to put the next variable after it in it's own bucket. A lot of this is implementation defined because the abstract machine that C++ models doesn't care. — NathanOliver, Oct 17 '19 at 16:44

score 3 · Answer 2 · answered Oct 17 '19 at 14:57

So imagine you have an 8 bit number, it's an uint8_t, and its value is set to 4. This would probably be stored as a = 0000 0100. Now, let's say you wish to convert this into a 16 bit number. What would happen? You have to assign some values to 'new' bits in this number. How would you assign them? You can't randomly assign zeros or ones, value of original variable will change. Depending on architecture etc. you have to pad value with extra bits. In my case, that would mean additional eight extra zeros be added in front of original MSB (most significant bit), making our number a = 0000 0000 0000 0100.

Value is still 4, but now you can assign anything in [0, 2^16) range, instead of [0, 2^8) range.

score 2 · Answer 3 · answered Oct 17 '19 at 14:54

2

bit padding:
Bit padding is the addition of one or more extra bits to a transmission or storage unit to make it conform to a standard size.

As the definition you posted is already correct, I'll try to explain with an example:

Suppose you have to store data that occupies less than 32 bits but you have 4 byte slots. It is easier to access that data by accessing to each slot, so you just have to complete all the 32 bits. The additional bits needed to complete 'the given space' but which are not part of the data conform the bit padding.

I'm sure there may be better examples of this in multiple contexts. Anybody, feel free to edit and/or complete the answer with new improvements or examples.

Hope this helps!

answered Oct 17 '19 at 14:54

89f3a1c

1,430
1
14
24

While i see, you want to help me very much and your style is very elegant, for which i am very thankful by the way;-), i still don´t get it. You say `Suppose you have to store data that occupies less than 32 bits but you have 4 byte slots` thats is what i understand. But at `It is easier to access that data by accessing to each slot, so you just have to complete all the 32 bits.` i don´t quite understand what you mean exactly. 1. Why do i need to access every byte of an `int32_t` var f.e. on its own exactly and how do i do that? 2. Why i have to complete all 32 bits by accessing through bytes? – RobertS supports Monica Cellio Oct 17 '19 at 15:40
Was about to answer your comment, but just saw Nathan's answer which addresses all this in great depth and with examples. Is there any left or is that the answer you've been loking for? – 89f3a1c Oct 17 '19 at 19:52

score 0 · Answer 4 · answered Oct 17 '19 at 15:01

Bit Padding can be used in multiple contexts. Two common examples are network, and encryption. I believe the encryption context is more relevant.

Padding is used in encryption to make it harder to decipher messages, which have common part. If multiple messages are known to have same prefix (e.g., "hello"), it make it easier to break the key. By "padding" the message with a variable length bit field, it make it much harder to break the key.

It is being told the British intelligence was able to speed up the analysis of Enigma message, because the German were starting their message with the same heading.

For more technical, accurate description: https://en.wikipedia.org/wiki/Padding_(cryptography) Look for the section about block cipher, and bit padding

How bit padding is used in case of memory storage? – RobertS supports Monica Cellio Oct 17 '19 at 15:10 — RobertS supports Monica Cellio, Oct 17 '19 at 15:10
The example in my answer literally answers that question ;) – 89f3a1c Oct 17 '19 at 15:12 — 89f3a1c, Oct 17 '19 at 15:12

What is "bit padding" or "padding bits" exactly?

bit padding:

Background:

4 Answers4

Linked