Body

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, all numbers are double precision 64 bit floating-point numbers based on IEEE 754 standard, which refer to Wikipedia pictures. Its structure 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.

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	Shift the binary form of a to the left of bit B (< 32) and fill the right with 0.
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 examples of AND and OR, 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 executing r | w | x, the three bits of user are all 1, indicating that all three permissions have been obtained.

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 you can see before, you can judge whether the user has the permission by 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, which has read and write permissions. Now, if you want to delete the read permission, in essence, reset the 1 in the third place to 0, and change 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 stands for the position of 1 in 32-bit binary number (the rest are all 0); index stands for permission space, which is used to break the limit of JavaScript digit number. 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, like 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 the introduction of the concept of permission space to break through the limitation of the number of bits in binary operation, you can also use the bignumber of math.js to directly calculate the binary number of more than 32 bits. See its documents for details, which will not be discussed in detail here.

5. Applicable scenarios and problems

If a permission system is designed according to the most widely used RBAC model, there are usually several entities: application, permission, role and 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 a 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 permission point is 2, 3, 5, 7, 11, and the user permission is 5 * 7 * 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.