Mask (computing)
468313
224377069
2008-07-08T16:12:48Z
134.253.26.10
/* Masking bits to 0 */
In [[computer science]], a '''mask''' is data that is used for [[bitwise operations]].
Using a mask, multiple bits in a byte, nibble, word (etc.) can be set either on, off or inverted from on to off (or vice verse) in a single bitwise operation.
==Common bitmask functions==
===Masking bits to <code>1</code>===
To turn certain bits on, the [[Logical disjunction|bitwise <code>OR</code>]] operation can be used. [[Logical disjunction#Bitwise operation|Recall]] that <code>Y or 1 = 1</code> and <code>Y or 0 = Y</code>. Therefore, to make sure a bit is on, <code>OR</code> can be used with a <code>1</code>. To leave a bit alone, <code>OR</code> is used with a <code>0</code>.
e.g.
1001'''1'''101 1001'''0'''101
OR 0000'''1'''000 0000'''1'''000
= 1001'''1'''101 1001'''1'''101
===Masking bits to <code>0</code>===
As seen above, there is no way to change a bit from ''on'' to ''off'' using the <code>OR</code> operation. Instead, [[Binary and|bitwise <code>AND</code>]] is used. When a value is <code>AND</code>ed with a <code>1</code>, the result is simply the original value, as in: <code>Y AND 1 = Y</code>. However, <code>AND</code> with a value with <code>0</code>, is guaranteed to get a <code>0</code> back so it is possible to turn a bit off by <code>AND</code>ing it with <code>0</code>: <code>Y AND 0 = 0</code>. To leave the other bits alone, <code>AND</code>ing them with a <code>1</code> can be done.
The most common mask used, also known as a '''bitmask''', extracts the status of certain bits in a binary string or number (a [[bit field]] or [[bit array]]). For example, to extract the status of the fifth bit from the binary string <code>10011101</code> (counting from the MSB) it is possible to use a bitmask such as <code>00001000</code> and use the [[Binary and|bitwise <code>AND</code>]] operator. Recalling that <code>1 AND 1 = 1</code>, with <code>0</code> otherwise, finds the status of the fifth bit, since
1001'''1'''101 1001'''0'''101
AND 0000'''1'''000 0000'''1'''000
= 0000'''1'''000 0000'''0'''000
===Querying the status of a bit===
It is possible to use bitmasks to easily check the state of individual bits regardless of the other bits. To do this, turning off all the other bits using the bitwise <code>AND</code> is done as discussed [[#Masking bits to 0|above]] and the value is compared with <code>0</code>. If it is, then the bit was off, but if the value is any other value, then the bit was on. What makes this convenient is that it is not necessary to figure out what the value actually is, just that it is not <code>0</code>.
===Toggling bit values===
So far the article has covered how to turn bits on and turn bits off, but not both at once. Sometimes it is not really cared what the value is, it must be made the opposite of what it currently is. This can be achieved using the [[Exclusive or|<code>XOR</code> (exclusive or)]] operation. <code>XOR</code> returns <code>1</code> [[iff|if and only if]] an [[odd number]] of bits are <code>1</code>. Therefore, if two corresponding bits are <code>1</code>, the result will be a <code>0</code>, but if only one of them is <code>1</code>, the result will be <code>1</code>. Therefore inversion of the values of bits is done by <code>XOR</code>ing them with a <code>1</code>. If the original bit was <code>1</code>, it returns <code>1 XOR 1 = 0</code>. If the original bit was <code>0</code> it will get <code>0 XOR 1 = 1</code>. Also note that <code>XOR</code> masking is bit-safe, meaning it will not affect unmasked bits because <code>Y XOR 0 = Y</code>, just like an <code>OR</code>.
==Uses of bitmasks==
=== Arguments to functions ===
In programming languages such as [[C (language)|C]], bit masks are a useful way to pass a set of named boolean arguments to a function. For example, in the graphics API [[OpenGL]], there is a command, <code>glClear()</code> which clears the screen or other buffers. It can clear up to four buffers (the color, depth, accumulation, and stencil buffers), so the API authors could have had it take four arguments. But then a call to it would look like
glClear(1,1,0,0); // This is not how glClear actually works and would make for unreadable code.
which is not very descriptive. Instead there are four defined field bits, <code>GL_COLOR_BUFFER_BIT</code>, <code>GL_DEPTH_BUFFER_BIT</code>, <code>GL_ACCUM_BUFFER_BIT</code>, and <code>GL_STENCIL_BUFFER_BIT</code> and <code>glClear()</code> is declared as
void glClear(GLbitfield mask);
Then a call to the function looks like this
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
Internally, a function taking a bitfield like this can use binary <code>and</code> to extract the individual bits. For example, an implementation of <code>glClear()</code> might look like:
<source lang="c">
void glClear(GLbitfield mask) {
if (mask & GL_COLOR_BUFFER_BIT) {
// Clear color buffer.
}
if (mask & GL_DEPTH_BUFFER_BIT) {
// Clear depth buffer.
}
if (mask & GL_ACCUM_BUFFER_BIT) {
// Clear accumulation buffer.
}
if (mask & GL_STENCIL_BUFFER_BIT) {
// Clear stencil buffer.
}
}</source>
The advantage to this approach is that function argument overhead is decreased. Since the minimum datum size is one byte, separating the options into separate arguments would be wasting seven bits per argument and would occupy more stack space. Instead, functions typically accept one or 32-bit integers, with up to 32 option bits in each. While elegant, in the simplest implementation this solution is not [[type safety|type-safe]]. A <code>GLbitfield</code> is simply defined to be an <code>unsigned int</code>, so the compiler would allow a meaningless call to <code>glClear(42)</code> or even <code>glClear(GL_POINTS)</code>. In [[C++]] an alternative would be to create a class to encapsulate the set of arguments that glClear could accept and could be cleanly encapsulated in a library (see the external links for an example).
===Inverse Masks===
Masks are used with IP addresses in IP ACLs (Access Control Lists) to specify what should be permitted and denied. Masks in order to configure IP addresses on interfaces start with 255 and have the large values on the left side, for example, IP address 209.165.202.129 with a 255.255.255.224 mask. Masks for IP ACLs are the reverse, for example, mask 0.0.0.255. This is sometimes called an inverse mask or a wildcard mask. When the value of the mask is broken down into binary (0s and 1s), the results determine which address bits are to be considered in processing the traffic. A 0 indicates that the address bits must be considered (exact match); a 1 in the mask is a "don't care". This table further explains the concept.
Mask Example
network address (traffic that is to be processed)
10.1.1.0
mask
0.0.0.255
network address (binary)
00001010.00000001.00000001.00000000
mask (binary)
00000000.00000000.00000000.11111111
Based on the binary mask, it can be seen that the first three sets (octets) must match the given binary network address exactly (00001010.00000001.00000001). The last set of numbers are "don't cares" (.11111111). Therefore, all traffic that begins with 10.1.1. matches since the last octet is "don't care". Therefore, with this mask, network addresses 10.1.1.1 through 10.1.1.255 (10.1.1.x) are processed.
Subtract the normal mask from 255.255.255.255 in order to determine the ACL inverse mask. In this example, the inverse mask is determined for network address 172.16.1.0 with a normal mask of 255.255.255.0.
255.255.255.255 - 255.255.255.0 (normal mask) = 0.0.0.255 (inverse mask)
ACL equivalents
The source/source-wildcard of 0.0.0.0/255.255.255.255 means "any".
The source/wildcard of 10.1.1.2/0.0.0.0 is the same as "host 10.1.1.2"
===Image masks===
[[Image:Blit_dot.gif|thumb|[[Raster graphics|Raster graphic]] [[Sprite (computer graphics)|sprite]]s (left) and masks (right)]]
In [[computer graphics]], when a given image is intended to be placed over a background, the transparent areas can be specified through a binary mask. This way, for each intended image there are actually two [[bitmap]]s: the actual image, in which the non used areas are given a [[pixel]] value with all [[bit]]s set to 0's, and an additional ''mask'', in which the correspondent image areas are given a pixel value of all bits set to 0's and the surrounding areas a value of all bits set to 1's. In the sample at right, black pixels have the all-zero bits and white pixels have the all-one bits.
At [[runtime|run time]], to put the image on screen over the background, the program first masks the screen pixel's bits with the image mask at the desired coordinates using the [[bitwise AND]] operation. This preserves the background pixels of the transparent areas while reset with zeros the bits of the pixels which will be obscured by the overlapped image.
Then, the program renders the image pixels' bits by blending them with the background pixels' bits using the [[Logical disjunction|bitwise OR]] operation. This way, the image pixels are appropiately placed while keeping the background surrounding pixels preserved. The result is a perfect compound of the image over the background.
[[Image:Sprite rendering by binary image mask.png|center]]
This technique is used for painting pointing devices' cursors; in typical 2-D videogames for characters, bullets and so on (the [[Sprite (computer graphics)|sprite]]s); [[GUI]] [[Icon (computing)|icon]]s; video titling and other image mixing applications.
Although related (due to being used for the same purposes), [[Palette (computing)#Transparent color in palettes|transparent color]]s and [[alpha channel]]s are techniques which do not involve the image pixels' mixage by binary masking.
===Hash tables===
To create a hashing function for a [[hash table]] often a function is used that has a large domain. To create an index from the output of the function, a modulo can be taken to reduce the size of the domain to match the size of the array, however it is often faster on many processors to restrict the size of the hash table to powers of two sizes and use a bit mask instead.
==See also==
*[[Affinity mask]]
*[[Subnetwork]]
*[[Bit manipulation]]
== External links ==
*[http://bitwise-enum.googlecode.com bit_enum: a type-safe C++ library for bitwise operations]
[[Category:Computer arithmetic]]
[[de:Bitmaske]]
[[es:Máscara (informática)]]
[[lv:Maska (datorzinātnē)]]
[[pl:Maska bitowa]]
[[ro:Mascare binară]]
[[ru:Битовая маска]]
[[sv:Mask (dator)]]