Bit operation and permission design in JavaScript

1. Content summary

This paper mainly discusses the following two problems:

  • Bit operation of JavaScript: first, simply review the lower bit operation, which is usually used less. I believe that many people forget about it as much as I do
  • Authority Design: according to the characteristics of bit operation, design a authority system (add, delete, judge, etc.)

2. JavaScript bit operation

2.1. Number

Before we talk about bit operation, let's take a look at the Number in JavaScript, which we need to use later.

In JavaScript, the numbers are Double precision 64 bit floating point number based on IEEE 754 standard The structure of Wikipedia is as follows:

  • sign bit: used to indicate a sign
  • exponent: used to express the power
  • mantissa: used to express precision

That is, a number can only range from - (2 ^ 53 - 1) to 2 ^ 53 - 1.

Now that we have reached this point, let's say one more thing: 0.1 + 0.2 is not accurate because of this. When the floating point number is expressed in binary, it is infinite and has 53 bits at most. It must be truncated to produce errors. The simplest solution is to enlarge a certain number of times into an integer, and then reduce it after calculation. But a safer way is to use what will be mentioned below math.js Etc.

There are also four decimal places:

// Decimal system
123456789
0

// Binary: prefix 0B, 0B
0b10000000000000000000000000000000 // 2147483648
0b01111111100000000000000000000000 // 2139095040
0B00000000011111111111111111111111 // 8388607

// Octal: prefix 0O, 0O (previously supported prefix 0)
0o755 // 493
0o644 // 420

// Hex: prefix 0X, 0X
0xFFFFFFFFFFFFFFFFF // 295147905179352830000
0x123456789ABCDEF   // 81985529216486900
0XA                 // 10

OK, so much for Number. Let's see the bit operation in JavaScript.

2.2. Bit operation

Bitwise operators treat their operands as 32-bit bit sequences (consisting of 0 and 1) and return values are still standard JavaScript values. The bitwise operators in JavaScript are:

operator usage describe
Bitwise AND a & b For each bit, only when the corresponding bit of two operands is 1, the result is 1, otherwise 0.
Bitwise OR `a \ b` For each bit, when there is at least one bit corresponding to two operands, the result is 1, otherwise 0.
XOR (XOR) a ^ b For each bit, when there is only one 1 corresponding to two operands, the result is 1, otherwise 0.
Bitwise NOT ~a Reverse the bit of the operand, i.e. 0 becomes 1, 1 becomes 0.
Left shift a << b Move the binary form of a to B (< 32) bit to the left, and fill with 0 to the right.
Signed shift right a >> b Move the binary representation of a to the right by B (< 32) bits, and discard the moved bits.
unsigned right shift a >>> b Move the binary representation of a to the right by B (< 32), discard the moved bits, and fill the left with 0.

Here are a few examples, mainly looking at AND and OR:

# Example 1
    A = 10001001
    B = 10010000
A | B = 10011001

# Example 2
    A = 10001001
    C = 10001000
A | C = 10001001
# Example 1
    A = 10001001
    B = 10010000
A & B = 10000000

# Example 2
    A = 10001001
    C = 10001000
A & C = 10001000

3. Use of bit operation in permission system

In the traditional permission system, there are many relationships, such as the relationship between user and permission, the relationship between user and role. The larger the system is, the more relationships it has, the more difficult it is to maintain. The introduction of bit operation can solve this problem skillfully.

Before we talk about "the use of bit operation in permission system", we first assume two premises. All the following discussions are based on these two premises:

  1. Each permission code is unique (this is obvious)
  2. Binary number form of ownership limit code, with and only one bit value of 1, and the rest are all 0 (2^n)

If the user's authority AND authority code are all represented by two-level numbers, AND combined with the above AND OR examples, it is not difficult to find out the characteristics of bit operation:

  • |Can be used to grant permissions
  • &Can be used to verify permissions

In order to make it more clear, the file permissions of Linux can be divided into read, write and execute, with various forms such as letters and numbers

Jurisdiction Alphabetic representation Digital representation Binary system
read r 4 0b100
write w 2 0b010
implement x 1 0b001

As you can see, permissions are represented by 1, 2 and 4 (that is, 2^n). After conversion to binary, only one bit is 1, and the rest is 0. Let's take a few examples to see how to use the characteristics of binary to add, verify and delete permissions.

3.1. Add permission

let r = 0b100
let w = 0b010
let x = 0b001

// Assign all permissions to the user (use the | operation above)
let user = r | w | x

console.log(user)
// 7

console.log(user.toString(2))
// 111

//     r = 0b100
//     w = 0b010
//     r = 0b001
// r|w|x = 0b111

As you can see, after r | w | x is executed, the three bits of user are all 1, indicating that all three permissions have been obtained.

When there is a permission problem under Linux, the crudest solution is chmod 777 xxx. Here, 7 represents: readable, writable, and executable. The three seven represent: the owner of the file, the group of the owner of the file, and all other users.

3.2. Verification authority

Just now, we have demonstrated the addition of permissions. The following shows permission verification:

let r = 0b100
let w = 0b010
let x = 0b001

// Give the user two rights of r w
let user = r | w
// user = 6
// user = 0b110 (binary)

console.log((user & r) === r) // true has r permission
console.log((user & w) === w) // true has w permission
console.log((user & x) === x) // false NO x permission

As we have seen before, we can judge whether the user has the permission by the user permission & permission code = = = permission code.

3.3. Delete permission

We talked about using | to give permissions, using & to judge permissions, then what about deleting permissions? The essence of deleting permission is to reset 1 at the specified location to 0. In the previous ex amp le, the user's permission is 0b110. He has read and write permissions. Now he wants to delete the read permission. In essence, he resets the 1 in the third place to 0 and changes it to 0b010:

let r = 0b100
let w = 0b010
let x = 0b001

let user = 0b010;

console.log((user & r) === r) // false no r permission
console.log((user & w) === w) // true has w permission
console.log((user & x) === x) // false NO x permission

So how to operate? In fact, there are two schemes. The simplest one is XOR ^. According to the introduction above, "when there is only one bit corresponding to two operands, the result is 1, otherwise it is 0". So XOR is actually a toggle operation. If there is no increase, there will be decrease:

let r    = 0b100
let w    = 0b010
let x    = 0b001
let user = 0b110 // There are two permissions of r w

// Perform exclusive or operation, delete r permission
user = user ^ r

console.log((user & r) === r) // false no r permission
console.log((user & w) === w) // true has w permission
console.log((user & x) === x) // false NO x permission

console.log(user.toString(2)) // Now user is 0b010

// Perform another exclusive or operation
user = user ^ r

console.log((user & r) === r) // true has r permission
console.log((user & w) === w) // true has w permission
console.log((user & x) === x) // false NO x permission

console.log(user.toString(2)) // Now user changes back to 0b110

So what if you just want to delete the permissions (instead of adding if you have none, and subtracting if you have one)? The answer is to execute & (~ code), reverse, and then execute and operate:

let r    = 0b100
let w    = 0b010
let x    = 0b001
let user = 0b110 // There are two permissions of r w

// Remove r permission
user = user & (~r)

console.log((user & r) === r) // false no r permission
console.log((user & w) === w) // true has w permission
console.log((user & x) === x) // false NO x permission

console.log(user.toString(2)) // Now user is 0b010

// Do it again
user = user & (~r)

console.log((user & r) === r) // false no r permission
console.log((user & w) === w) // true has w permission
console.log((user & x) === x) // false NO x permission

console.log(user.toString(2)) // Now the user is still 0b010 and will not be added

4. Limitations and Solutions

Previously, we reviewed the Number and bit operation in JavaScript, and understood the principle of permission system based on bit operation and the instance of Linux file system permission.

All of the above have preconditions: 1. Each permission code is unique; 2. The binary number form of each permission code has and only one bit value is 1 (2^n). In other words, the permission code can only be 1, 2, 4, 8,..., 1024,... As mentioned above, the range of a number can only be between - (2 ^ 53-1) and 2 ^ 53-1, and the bitwise operators of JavaScript regard their operands as 32-bit sequences. Then the number of permissions available for the same application is very limited. This is also the limitation of the programme.

In order to break through this limitation, a concept called "permission space" is proposed here. Since the number of permissions is limited, it is advisable to open more space for storage.

Based on the permission space, we define two formats:

  1. Permission code, string, like index,pos. pos represents the position of 1 in the 32-bit binary number (the rest are all 0); index represents the permission space, which is used to break the limit of the number of JavaScript digits. It is a positive integer starting from 0. Each permission code should belong to a permission space. Index and pos are separated by commas.
  2. User permission, string, such as 1, 16, 16. A comma separates the permission values of each permission space. For example, 1, 16, 16 means that the permission value of permission space 0 is 1, the permission value of permission space 1 is 16, and the permission of permission space 2 is 16.

It may not be easy to understand, directly on the code:

// User's permission code
let userCode = ""

// Suppose you have these permissions in the system
// Pure simulation, normally in order, such as 0,0 0,1 0,2..., occupy one permission space as much as possible, and then use the next
const permissions = {
  SYS_SETTING: {
    value: "0,0",   // index = 0, pos = 0
    info: "System permissions"
  },
  DATA_ADMIN: {
    value: "0,8",
    info: "Database permissions"
  },
  USER_ADD: {
    value: "0,22",
    info: "New user permission"
  },
  USER_EDIT: {
    value: "0,30",
    info: "User edit permission"
  },
  USER_VIEW: {
    value: "1,2",   // index = 1, pos = 2
    info: "User view permission"
  },
  USER_DELETE: {
    value: "1,17",
    info: "User delete permission"
  },
  POST_ADD: {
    value: "1,28",
    info: "Article new permission"
  },
  POST_EDIT: {
    value: "2,4",
    info: "Article editing permission"
  },
  POST_VIEW: {
    value: "2,19",
    info: "Article view permission"
  },
  POST_DELETE: {
    value: "2,26",
    info: "Article delete permission"
  }
}

// add permission
const addPermission = (userCode, permission) => {
  const userPermission = userCode ? userCode.split(",") : []
  const [index, pos] = permission.value.split(",")

  userPermission[index] = (userPermission[index] || 0) | Math.pow(2, pos)

  return userPermission.join(",")
}

// Delete permission
const delPermission = (userCode, permission) => {
  const userPermission = userCode ? userCode.split(",") : []
  const [index, pos] = permission.value.split(",")

  userPermission[index] = (userPermission[index] || 0) & (~Math.pow(2, pos))

  return userPermission.join(",")
}

// Judge whether there is authority
const hasPermission = (userCode, permission) => {
  const userPermission = userCode ? userCode.split(",") : []
  const [index, pos] = permission.value.split(",")
  const permissionValue = Math.pow(2, pos)

  return (userPermission[index] & permissionValue) === permissionValue
}

// List all permissions the user has
const listPermission = userCode => {
  const results = []

  if (!userCode) {
    return results
  }

  Object.values(permissions).forEach(permission => {
    if (hasPermission(userCode, permission)) {
      results.push(permission.info)
    }
  })

  return results
}

const log = () => {
  console.log(`userCode: ${JSON.stringify(userCode, null, " ")}`)
  console.log(`Permission list: ${listPermission(userCode).join("; ")}`)
  console.log("")
}

userCode = addPermission(userCode, permissions.SYS_SETTING)
log()
// userCode: "1"
// Permission list: system permission

userCode = addPermission(userCode, permissions.POST_EDIT)
log()
// userCode: "1,,16"
// Permission list: system permission; article editing permission

userCode = addPermission(userCode, permissions.USER_EDIT)
log()
// userCode: "1073741825,,16"
// Permission list: system permission; user editing permission; article editing permission

userCode = addPermission(userCode, permissions.USER_DELETE)
log()
// userCode: "1073741825,131072,16"
// Permission list: system permission; user edit permission; user delete permission; Article edit permission

userCode = delPermission(userCode, permissions.USER_EDIT)
log()
// userCode: "1,131072,16"
// Permission list: system permission; user delete permission; Article edit permission

userCode = delPermission(userCode, permissions.USER_EDIT)
log()
// userCode: "1,131072,16"
// Permission list: system permission; user delete permission; Article edit permission

userCode = delPermission(userCode, permissions.USER_DELETE)
userCode = delPermission(userCode, permissions.SYS_SETTING)
userCode = delPermission(userCode, permissions.POST_EDIT)
log()
// userCode: "0,0,0"
// Permission list: 

userCode = addPermission(userCode, permissions.SYS_SETTING)
log()
// userCode: "1,0,0"
// Permission list: system permission

In addition to introducing the concept of permission space to break through the number limit of binary operation, you can also use math.js We can directly calculate the binary number of more than 32 bits. For details, please refer to its documents. We won't go into details here.

5. Applicable scenarios and problems

If the most widely used RBAC Model design permission system, then there are generally several entities: application, permission, role, user. User permissions can come directly from permissions or from roles:

  • Multiple permissions under an application
  • Permissions and roles are many to many relationships
  • Users and roles are many to many relationships
  • Users and permissions are many to many relationships

In this model, there are generally corresponding tables of users and permissions, users and roles, roles and permissions. Imagine a back-end authority management system in a mall. There may be tens of thousands or even hundreds of thousands of stores (Applications). Each store may have dozens of users, roles and authorities. With the continuous development of the business, the three corresponding tables just mentioned will become larger and harder to maintain.

The method of base conversion can omit the corresponding relation table, reduce the query and save the space. Of course, there is no harm in omitting the corresponding relationship, for example, the following questions:

  • How to find my permission efficiently?
  • How to find all users with certain permission efficiently?
  • How to control the validity of permissions?

Therefore, the scheme of base conversion is more suitable for the scenario where there are many applications just mentioned, and the number of users, permissions and roles in each application is less.

6. Other programs

In addition to binary scheme, of course, there are other schemes that can achieve similar effects. For example, directly use A string composed of 1 and 0. The permission point corresponds to index. 1 means permission, and 0 means no permission. For example: add 0, delete 1, and edit 2. If user A has the right to add and edit, then userCode is 101; user B has all the right, and userCode is 111. This scheme is simpler than binary conversion, but it wastes space.

There is also the scheme of using prime numbers. All the permission points are prime numbers, and the user permission is the product of all the permission points he has. For example, the authority point is 2, 3, 5, 7, 11, and the user authority is 57 11 = 385. The trouble of this scheme is to obtain prime number (New permission point) and prime factor decomposition (judgment permission). When there are many permission points, it will become RSA quickly. If only adding, deleting, modifying and querying a few permissions, it can be considered.

7. reference

This article was published from Netease cloud music front end team Welcome to reprint freely. Please keep the source. We've been recruiting people. If you happen to be ready to change jobs and you happen to like cloud music, then Join us!

Tags: Javascript REST Linux less

Posted on Wed, 06 Nov 2019 18:20:06 -0800 by LiamG