How to calculate password complexity

I'd recommend using cracklib for this.

Using something like cracklib is very good if you can afford the time of checking against all of the potential rules. If you just want something quick -- say for a javascript-based strength meter -- then consider estimating the number of potential guesses that would be required for a brute force attack. For every character type seen update a multiplier based on the number of potential characters of that type. So if you have only digits, then the multiplier would be 10. If you have only lowercase, then the multiplier is 26. If both, then the multiplier is 36 -- that is for each character in the password, a brute force attack would need to try up to 36 different characters. A password containing both upper and lowercase characters, digits, and punctuation, then would have a multiplier of 10 + 26 + 26 + 32 = 94 (more or less depending on the allowable punctuation).

To estimate the maximum number of permutations a brute force method would take, raise the multiplier to the power equal to the number of digits in the password. This gives you then maximum number of guesses it would take to break the password using a brute force attack. Assume that each guess takes one cpu cycle and given the fastest processor calculate how long it would take to break a password given a certain number of permutations. For example, if my multiplier was 10 and the password was 10 characters long, then I would have 10,000,000,000 potential combinations. On 3GHz processor, this ought to take 10/3 * k or 3k seconds (where k is the number of cycles per guess, typically small). Clearly, this is a weak password.

Now, establish some ranges that represent reasonable password strengths. For example, if you think that an 8 character password with upper and lowercase characters is minimally required for medium strength, then your cutoff would be 52^8 or approximately 1.5 years on a 3GHz processor (assuming k = 1). If you add in digits, then the cutoff becomes 62^8 or approximately 8 years on 3GHz processor.

To put it in use, then you only need keep track of which kinds of characters you see, construct the appropriate multiplier, calculate the expected permutations based on password length, and compare it against your predefined cutoffs to determine what strength the password has.